G2 - Genuine Multiple Dependencies [Hard]

2 secs 1024 MB
uni_kakurenbo

問題 G1 とは制約のみが異なります

問題文


G1 - Genuine Multiple Dependencies [Easy] と同じ状況を考えます

下記の制約下で問題を解いてください.

  • 入力はすべて整数である

サンプル


G1 と同一のものです.

入力例1
11
0 1
1 1
1 3
2 6
2 10
6 8
5 14
12 7
14 21
0 300
300 1
出力例1
1
1
3
21
55
1716
8568
18564
393731287
1
1

Submit


Go (1.14)