AT_arc035_d [ARC035D] 高橋くんとマラソンコース

[problemUrl]: https://atcoder.jp/contests/arc035/tasks/arc035_d 高橋くんはマラソン大会の主催者で、今度開くマラソン大会の計画案を練っています。 高橋くんの住む街には東西と南北に伸びるそれぞれ $ 10^6 $ 本の道があり、南北に伸びる道のうち西から $ x $ 番目の道と、東西に伸びる道のうち南から $ y $ 番目の道が交わる交差点を $ (x,y) $ と表します。 マラソンコースの作りを簡単にするため、道は東か北の方向へのみ進めるようにしました。 高橋くんはマラソンコースで参加者のタイム計測に使える場所として、$ N $ 個のチェックポイント $ (p_i,q_i) $ を決めました。 高橋くんの街では、参加者はマラソン大会で一人ひとりが違った経路を取りたがるため、コースの異なる経路の数が重要です。 タイム計測の必要から、チェックポイント $ u $ からチェックポイント $ v\ (u\

入力は以下の形式で標準入力から与えられる。 > $ 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}\

種類 $ 2 $ のクエリに対する答えを $ 1 $ 行ずつクエリの与えられた順に出力せよ。チェックポイント $ l_{1j} $ から チェックポイント $ r_{1j} $ までの経路のほうが多い時は `FIRST`、チェックポイント $ l_{2j} $ からチェックポイント $ r_{2j} $ までの経路のほうが多い時は `SECOND` と出力せよ。 末尾の改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。 - $ 30 $ 点分のテストケースにおいて、$ 2≦N≦1,000,\ 1≦Q≦1,000 $ を満たす。 ### Sample Explanation 1 $ 1 $ 番目のクエリでは、チェックポイント$ 1 $ からチェックポイント$ 3 $ までの経路の数は、以下のように $ 5 $ つである。 !\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample1.png)!\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample2.png)!\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample3.png)!\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample4.png)!\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample5.png) チェックポイント $ 3 $ からチェックポイント $ 4 $ までの経路の数は、以下のように $ 2 $ つである。 !\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample6.png)!\[\](http://arc035.contest.atcoder.jp/img/arc/035/D\_sample7.png) よって、`FIRST` と出力する。 $ 2 $ 番目のクエリでは、経路の数はそれぞれ $ 5 $ と $ 10 $ なので、`SECOND` と出力する。 $ 3 $ 番目のクエリでチェックポイント $ 2 $ の位置が変更された後、$ 4 $ 番目のクエリでは、経路の数はそれぞれ $ 10 $ と $ 2 $ なので、`FIRST` と出力する。 ### Sample Explanation 2 比べる数は非常に大きくなることに注意してください。