100 1000000000
0 1 61153166
1 2 113719784
2 1 126178940
1 2 84704700
4 2 63990037
5 2 82315137
3 1 94104156
4 2 67953618
3 2 134366078
6 2 217831760
5 2 161866599
9 2 326554356
11 1 347924435
8 1 59512164
12 2 717356288
6 2 245004266
13 2 376764166
16 1 234975521
10 2 220247525
13 2 407350025
9 2 212997897
12 2 287276242
12 1 578074160
11 1 272804886
7 2 212614016
25 2 432928033
20 2 327991486
21 1 462921171
14 2 249040364
26 1 362073791
26 1 1000000000
10 2 214348758
25 2 215961794
22 1 824468781
15 1 379523672
8 1 111776613
16 2 177081546
33 2 446273869
36 2 206107637
2 1 72541404
39 1 175237214
29 1 490798958
21 1 728295752
36 1 194315995
32 2 451317262
39 2 316300312
41 2 895939093
40 2 186035051
33 1 453557556
48 1 159412858
40 1 256289546
48 1 190956360
50 2 442731426
24 1 193378930
52 1 178451873
44 2 387762646
37 2 355458608
42 1 252434700
54 1 666007630
51 1 253425726
7 2 177758301
51 2 203039219
61 2 380297274
62 1 166851059
64 1 237359576
62 2 331338275
14 2 175021700
52 2 272364110
44 1 653293649
67 2 366915034
70 2 412330459
68 1 357378323
56 1 560800594
21 1 650326756
53 1 224490171
65 1 547913003
46 2 423918097
67 1 160434971
29 1 607281614
61 1 167036085
51 1 116143105
22 1 250987554
78 1 359142461
50 2 409101840
18 2 286653593
84 1 241233819
81 2 225952504
81 1 409146754
74 1 496514194
72 1 236923115
87 2 245104941
79 1 261789231
66 2 165338965
83 2 294409364
80 1 490952013
24 2 103441746
88 1 332191689
96 1 330086678
19 2 184488474
96 2 388762253