G2 - Genuine Multiple Dependencies [Hard]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

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

問題文

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

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

  • 1T1041 \leq T \leq \bold{10^4}
  • 0N30000 \leq N \leq \bold{3000}
  • 1X30001 \leq X \leq \bold{3000}
  • 入力はすべて整数である

サンプル

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.21)