input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

2
2
4
7
5
8
9
4
6
2
11
13
22
10
25
15
9
13
14
16
29
16
16
15
2
5
11
6
14
14
28
9
37
3
28
44
12
12
27
44
5
27
6
47
10
14
27
6
17
15
9
48
20
34
7
36
63
9
56
16
58
40
19
3
1
12
12
39
46
68
63
20
71
9
37
75
50
40
20
34
45
43
31
30
60
33
13
65
41
51
29
35
38
53
2
89
54
36
56
76
91
32
42
28
52
42
60
1
4
2...

result:

wrong answer 3rd numbers differ - expected: '3', found: '4'