数据范围是 $i,j\leq 10^5$。

数据（一般来说，过了下面的数据就能过题）

20 20
1 1
1 2
2 1
2 2
50 47
24 1
1 9
1 5
5 1
2 6
6 2
1 18
1 7
7 1
9999 9999
1 9999
20 20
340 3000
3000 340
500 101
1 1
9999 9998
87381 99999
99999 1
999999 999999
4846 77748
55340  6775
49617 83609
46093 78001
49174 69571
98505 35317
62198 51589
81502 48906
73145 71057
83440  1093
 4838 50126
29169  1380
79417  6729
31018 34000
81677   438
49381 61344
37408 19831
89505 98683
92177 39441
66228 54010
21108 30533
 1341   457
98777 81179
77040 90327
12378  9608
55146   652
12570  5578
76266  7141
71822 14041
61569 47150
51035 34504
 8476 25580
52557 14054
12047 50273
28591 11197
50004 37790
27056 95668
45806 24502
83045 30317
3322 98754
47977 60353
51624 97725
24720 66819
14673 40512
14206 34424

答案：

20 20 8
1 1 1
1 2 2
2 1 2
2 2 2
50 47 105
24 1 21
1 9 20
1 5 8
5 1 8
2 6 9
6 2 9
1 18 21
1 7 17
7 1 17
9999 9999 92
1 9999 262
20 20 8
340 3000 217
3000 340 217
500 101 144
1 1 1
9999 9998 92
87381 99999 333
99999 1 351
999999 999999 259
4846 77748 351
55340 6775 340
49617 83609 351
46093 78001 351
49174 69571 340
98505 35317 351
62198 51589 340
81502 48906 351
73145 71057 325
83440 1093 351
4838 50126 324
29169 1380 308
79417 6729 351
31018 34000 285
81677 438 351
49381 61344 340
37408 19831 324
89505 98683 333
92177 39441 351
66228 54010 335
21108 30533 308
1341 457 182
98777 81179 333
77040 90327 338
12378 9608 268
55146 652 340
12570 5578 268
76266 7141 340
71822 14041 340
61569 47150 340
51035 34504 324
8476 25580 282
52557 14054 340
12047 50273 324
28591 11197 308
50004 37790 314
27056 95668 351
45806 24502 324
83045 30317 351
3322 98754 351
47977 60353 340
51624 97725 351
24720 66819 340
14673 40512 324
14206 34424 311