P0798

三角板

三角板

zz 有一副神奇的三角板，分为宽型（Wide）和窄型（Narrow）。所有三角板均为等腰三角形：

  • 宽型三角板的底边长度是高的 22 倍；
  • 窄型三角板的底边长度与高相等。

zz 要将 nn 个三角板依次放在桌面上。桌面可以抽象为一条数轴。对于第 ii 个三角板，其底边位于直线 y=0y=0 上，顶点坐标为 (xi,yi)(x_i,y_i)。

若该三角板为宽型，则底边的两个端点分别为 (xi−yi,0)(x_i-y_i,0) 和 (xi+yi,0)(x_i+y_i,0)；若该三角板为窄型，则底边的两个端点分别为 (xi−yi2,0)(x_i-\frac{y_i}{2},0) 和 (xi+yi2,0)(x_i+\frac{y_i}{2},0)。

每成功放置一个三角板后，zz 都会统计当前可见的三角板顶点数量。如果一个顶点位于其他三角板内部或边界上，则该顶点不可见。

在尝试放置第 ii 个三角板时，如果其顶点 (xi,yi)(x_i,y_i) 已经位于某个已放置的三角板内部或边界上，则 zz 认为这个三角板无法放下，并且不会放置它。

请依次判断每个三角板能否放置，并在每次尝试后给出相应结果。

输入格式

第一行包含一个整数 nn，表示三角板的数量。

接下来 nn 行描述各个三角板。第 ii 行包含两个整数 xi,yix_i,y_i 和一个字符：

  • W 表示宽型三角板；
  • N 表示窄型三角板。

输出格式

输出 nn 行。

如果第 ii 个三角板能够放置，输出一个整数，表示放置该三角板后可见的顶点数量。

否则，输出字符串 FAIL。

样例输入

3
0 1 W
0 2 N
0 1 W

样例输出

1
1
FAIL

数据范围

  • 30%30\% 的数据满足 n≤103n\le 10^3；
  • 70%70\% 的数据满足 n≤4×104n\le 4\times 10^4；
  • 100%100\% 的数据满足 1≤n≤1051\le n\le 10^5；
  • 对于所有数据，−109≤xi≤109-10^9\le x_i\le 10^9，1≤yi≤1091\le y_i\le 10^9。

来源与许可

本题题面与测试数据整理自 BZOJ 2652。

样例 1

输入

3
0 1 W
0 2 N
0 1 W

输出

1
1
FAIL