/ 
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
高橋くんはマラソン大会の主催者で、今度開くマラソン大会の計画案を練っています。 高橋くんの住む街には東西と南北に伸びるそれぞれ 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
比べる数は非常に大きくなることに注意してください。