#arc038c. [arc038_c]茶碗と豆

[arc038_c]茶碗と豆

NN个大茶碗排成11列。 从左起,将0iN1(0≤i≤N-1)ii个茶碗称为茶碗ii。茶碗i1iN1i(1≤i≤N-1)上写着整数CiC_i,里面有AiA_ i个豆子。 茶碗00上没有写整数,也没有放豆子。 喜欢玩游戏的兄妹用这些茶碗和豆子玩游戏。

  • 玩家在自己的回合中,取出一个除了茶碗0以外的茶碗里的豆子。
  • 从碗i中取出豆子时,必须把豆子放进 茶碗iCii-C_ i,茶碗iCi+1i-C_ {i+1},…,茶碗i1i-1 的任意一个碗里。
  • 两个玩家轮流反复进行操作,在自己的回合里没有可以选择的豆子,玩家就输了(另一方玩家获胜)。

22人为了争夺胜利而采取最合适的战略时,先手和后手哪一方会获胜呢?

输入格式

输入以以下形式从标准输入提供。

N N

C1 C_1 A1 A_1

C2 C_2 A2 A_2

...

CN1 C_{N-1} AN1 A_{N-1}

  • 11行一个数NN表示茶碗个数的整数N2N105N(2≤N≤10^5)

  • 从第二行开始的N1N-1行提供茶碗的信息。其中,在第i1iN1i(1≤i≤N-1)行中提供两个整数Ci1CiiC i(1≤C i≤i)Ai0Ai109A_i(0≤A_i≤10^9)。这表示茶碗i上写的整数是CiC_i,中间放了AiA_i个豆子。但是,可以保证任意一个茶碗里都有豆子,即AiA_i的合计不等于00

输入输出样例

输入 #1

3
1 0
1 1

输出 #1

Second

输入 #2

7
1 1
2 0
1 0
2 0
4 1
3 0

输出 #2

First

输入 #3

7
1 1
2 0
1 9
2 10
4 3
3 5

输出 #3

Second

说明/提示

部分点

这个问题设置了部分点。

如果对满足N100N≤100Ai10A_i≤10的数据集11正确的情况下,则给予8080分。

如果对满足N100N≤100的数据集22进行了正确的情况下,另外给予2020分。

如果所有测试数据都正确,另外给予44分。

Sample Explanation 1 ゲームは、例えば以下のように進行します。 - 1ターン目:先手が茶碗 2 の豆を選んで取り出し、茶碗 1に豆を入れる - 2 ターン目:後手が茶碗 1 の豆を選んで取り出し、茶碗 0に豆を入れる - 3ターン目:豆を選ぶことができないため、先手の負けとなる この例の場合、各プレイヤーの行動の選択肢はどのターンにも 1 つしかないため必ずこのような結果となります。 Sample Explanation 2 ゲームは、例えば以下のように進行します。 - 1 ターン目:先手が茶碗 55 の豆を選んで取り出し、茶碗 4 に豆を入れる - 2ターン目:後手が茶碗 4 の豆を選んで取り出し、茶碗 2 に豆を入れる - 3 ターン目:先手が茶碗 2 の豆を選んで取り出し、茶碗 1 に豆を入れる - 4 ターン目:後手が茶碗 1 の豆を 1 つ選んで取り出し、茶碗 0 に豆を入れる - 5 ターン目:先手が茶碗 1 の豆を選んで取り出し、茶碗 0 に豆を入れる - 6ターン目:豆を選ぶことができないため、後手の負けとなる その他の進行でも、後手がどのような行動をとっても先手が適切な行動をとることによって勝つことができます。