10 1000000000
0 1 200065469
1 1 86267619
2 2 252169035
3 2 442282498
4 1 243844663
5 1 1000000000
6 2 144050751
7 2 158384200
8 1 174667458
9 1 782340303