100 1000000000
0 1 78946076
1 1 178201433
1 2 305193695
3 2 244974740
4 1 266716042
1 2 23378364
1 2 101299598
5 2 266565381
1 2 186234311
9 2 357425108
1 1 205646104
6 1 477249986
8 2 56651834
1 1 112275001
14 2 86180894
11 2 376302134
9 1 87144914
16 1 274961599
17 2 174356033
6 2 177998643
20 1 528692038
7 1 69605260
22 2 510967952
17 1 221323888
6 1 138425154
22 1 394848212
20 1 622739235
13 1 349850102
7 1 192252347
15 1 90689423
22 2 46397832
30 2 156957621
16 1 402040303
20 2 487763027
31 1 494021679
22 1 367915301
30 1 593099279
20 2 382580990
35 2 910708166
20 1 203156601
40 2 838873880
28 2 625074148
18 2 157399638
40 2 450081771
32 2 395784227
27 2 446197952
38 2 196641752
47 1 299948288
29 1 292940958
40 2 409511973
30 1 603921332
31 2 305764525
49 1 119067224
47 1 393688142
49 1 235413488
17 2 832074597
52 2 142659170
32 2 69378111
57 1 279151894
22 1 270366763
40 1 643923435
40 1 371256048
62 1 289203455
49 2 461959311
29 2 325092715
54 1 233474237
57 2 591823405
52 2 455494243
58 1 282534165
15 2 174708597
58 1 488241161
69 2 634361971
65 2 494095610
53 2 364319510
58 1 269593927
22 2 500095157
65 1 208830512
68 1 272182914
69 1 984325389
2 1 921724503
67 2 457281161
76 2 483209082
78 2 461579263
60 2 704873750
70 1 201340289
58 1 300044135
62 1 383040056
62 2 109909305
88 1 453401706
88 2 428398645
86 2 204953249
89 2 1000000000
91 2 343917693
88 2 771266508
85 2 585972745
77 1 488882227
95 2 315419342
96 2 582745052
75 2 410425619
86 2 252932387