10 1000000000
0 2 162993968
1 1 283390160
1 2 225721923
2 1 370915202
1 1 219893668
3 1 1000000000
5 2 386516393
5 2 915869674
2 1 387329124
1 2 895863273