100 1000000000
0 1 23430721
1 2 41155410
2 1 154924553
2 2 199287253
2 1 759322511
2 1 857571021
2 1 254362696
6 2 222758866
2 2 284553566
9 2 497147783
2 2 119801261
2 2 233978558
2 1 143496080
2 2 229187384
13 1 110307106
2 1 326880148
2 1 215743395
2 2 262011577
2 1 349735861
2 2 543348013
2 1 209794639
9 1 127967181
11 1 296771825
2 1 179228511
16 2 266818896
2 1 182802137
1 1 35784988
7 2 117827422
24 1 240312301
28 2 417354708
30 2 244113761
29 2 205785843
27 2 41015902
33 2 58892121
34 1 157253521
35 2 266423024
34 1 46425433
37 2 76202636
2 2 315295004
39 1 698887597
39 2 921825271
38 2 27369531
37 1 308287252
42 1 27926726
43 2 358874106
44 2 36123838
46 1 422528685
46 1 81051957
48 1 440809748
46 2 1000000000
48 1 29057930
51 2 61621526
52 2 61844910
53 1 36381765
54 1 40193027
54 1 228964937
55 2 51076328
57 1 54557846
58 2 62528412
59 2 98667378
59 1 605874390
61 1 467245739
59 2 121883339
59 2 29622624
64 1 85506323
65 2 102974945
66 1 35743690
67 1 449089075
67 2 270212265
67 1 229566208
67 1 211834734
67 1 162630085
67 2 154860794
67 1 168121543
67 2 540742660
67 2 142850003
67 1 87572327
67 2 327271933
67 2 230612385
67 1 146279457
71 1 501507621
80 2 179958002
67 1 234539203
67 2 232813554
67 2 280854466
67 1 366646765
84 1 211185523
76 1 531750075
87 2 224514161
85 1 448365320
73 1 579281198
79 2 246281674
72 2 412266611
80 1 122358987
67 2 213882321
95 1 183914366
77 2 257802077
67 2 338775430
95 1 316790468
97 2 395008681