問題文
高桥君是马拉松赛事的组织者,正在为即将举行的马拉松赛事制定计划。 高桥君住在一个东西南北延伸的小镇里。 10^6 有一条主干道,从西边的道路由北向南延伸。 x 南路及东西延伸路 y 第条路相交的路口 表示为 (x,y) 。
为了更轻松地创建马拉松路线,我们将路径设置为仅向东或向北。 高桥君是一个可以用来测量参与者在马拉松赛道上的时间的地方。N 检查点 我决定 (p_i,q_i) 。
在高桥君的镇上,赛道上不同路线的数量很重要,因为每个参与者都想在马拉松比赛中采取不同的路线。 由于需要测量时间而设置检查点 来自 u 的检查点 当将马拉松路线设置为 v (u < v) 时,u≦i≦v 检查点 i 参与者必须经历一切。
所以,高桥君做了以下事情: Q 疑问需要得到解答。
- k_j 检查点位置 更改为 (a_j,b_j) 。
- 检查点 最多 l_{1j} 的检查点 当将马拉松路线设置为 r_{1j} 的不同路线和检查点总数 确定 l_{2j} 的检查点 当将马拉松路线设置为 r_{2j} 之前的不同路线总数中哪一个较大。然而,较多的路线是 2 保证大于两倍。
请编写一个程序来帮助高桥君。
入力
输入将以以下格式从标准输入给出。
N p_1 q_1 p_2 q_2 : p_N q_N Q t_1 … : t_Q …
- 1 行包含一个表示检查点数量的整数。 N (2 ≦ N ≦ 2*10^5) 给出。
- 2 从线 N 行包含一个表示检查点位置的整数。 p_i, q_i(1 ≦ p_i, q_i ≦ 10^6) 用空格分隔。
- N+2 行包含一个表示查询数量的整数。 Q( 1 ≦ Q ≦ 2*10^5) 给出。
- N+3 从行 Q 行给出了查询。 表示第t_j 为 j 个查询的类型。 当
- t_j = 1 时,该行 k_j, a_j, b_j(1 ≦ k_j ≦ N, 1 ≦ a_j, b_j ≦ 10^6) 用空格分隔。
- t_j = 2 时,该行 l_{1j}, r_{1j}, l_{2j}, r_{2j} (1 ≦ l_{1j} < r_{1j} ≦ N, 1 ≦ l_{2j} < r_{2j} ≦ N ) 用空格分隔。
- 任何 i(1 ≦ i ≦ N-1) 的检查点 i 的检查点 当将马拉松路线设置为 i+1 的路径始终是(即使检查点位置在查询中发生变化)1 保证存在一个。此外,检查点位置不重叠。
部分点
针对此问题设置了部分分数。
- 30 在点的测试用例中, 查询的答案2≦N≦1,000, 1≦Q≦1,000 符合。
出力
種類 2 查询的答案 1 按照查询中给出的顺序输出每一行。检查站
来自 l_{1j} 的检查点
当有更多前往 r_{1j} 的路线时 FIRST,检查点
输出 l_{2j} 的检查点
当将马拉松路线设置为 r_{2j} 的路线时 SECOND 。
在第
不要忘记最后的换行符。
入力例1
4 1 1 2 5 4 5 5 6 4 2 1 3 3 4 2 1 3 1 4 1 2 2 2 2 2 3 3 4
出力例1
FIRST SECOND FIRST
1 个查询中,检查点 前往1 的检查点 当将马拉松路线设置为3 的路线数量如下: 5 一。

检查点 最多 3 的检查点 当将马拉松路线设置为 4 的路线数量如下: 2 一。

因此,
输出FIRST 。
对于第
2 个查询,路线数量为 5 和 10 所以,
第SECOND 。
对于第
3 个查询处的检查点 2 的位置改变后,4 个查询,路线数量为 10 和 2 所以,
第FIRST 。
对于第
入力例2
4 1 1 100 100 101 102 199 199 3 2 1 2 2 3 2 1 2 2 4 2 1 2 3 4
出力例2
FIRST FIRST FIRST
请注意,比较的数字可能非常大。