3
1 2 3 3
2 3 2 2
3 4 2 2
4
3 5
1 2
4 2
3 3
2
5 10 2 10
100 100 100 100
2
5 13
100 101
3
3 30 100 100
1 1 300 400
2 50 100 300
3
1 1
4 40
300 20
5
30 100000 4000 100005
2 4 5 80
2 4 5 41
100 100 101 101
100 120 130 140
5
1 1
4 40
4 42
300 100000
4001 3
10
10 10 99999 99999
100 100 89999 89999
1000 1000 79999 79999
10000 10000 69999 69999
100000 100000 599999 599999
200000 200000 49999 499999
300000 300000 39999 399999
310000 310000 380000 380000
350000 350000 370000 370000
360000 360000 360100 361000
11
360010 360010
350010 350010
310010 310010
301000 301000
201111 201111
101100 500123
80000 80000
1200 1200
200 200
30 30
1 999999
1
100 100 100 100
8
100 100
100 199
199 100
199 199
99 100
100 200
200 100
200 200
3
1 10 100 100
2 2 10 10
3 3 5 5
4
100 109
101 110
101 111
5 5
100
230 90000 4020 99176
271 400051 4062 401927
312 400071 4104 401978
353 400091 4146 402029
394 400111 4188 402080
435 400131 4230 402131
476 400151 4272 402182
517 400171 4314 402233
558 400191 4356 402284
599 400211 4398 402335
640 400231 4440 402386
681 400251 4482 402437
722 400271 4524 402488
763 400291 4566 402539
804 400311 4608 402590
845 400331 4650 402641
886 400351 4692 402692
927 400371 4734 402743
968 400391 4776 402794
1009 400411 4818 402845
1050 400431 4860 402896
1091 400451 4902 402947
1132 400471 4944 402998
1173 400491 4986 403049
1214 400511 5028 403100
1255 400531 5070 403151
1296 400551 5112 403202
1337 400571 5154 403253
1378 400591 5196 403304
1419 400611 5238 403355
1460 400631 5280 403406
1501 400651 5322 403457
1542 400671 5364 403508
1583 400691 5406 403559
1624 400711 5448 403610
1665 400731 5490 403661
1706 400751 5532 403712
1747 400771 5574 403763
1788 400791 5616 403814
1829 400811 5658 403865
1870 400831 5700 403916
1911 400851 5742 403967
1952 400871 5784 404018
1993 400891 5826 404069
2034 400911 5868 404120
2075 400931 5910 404171
2116 400951 5952 404222
2157 400971 5994 404273
2198 400991 6036 404324
2239 401011 6078 404375
2280 401031 6120 404426
2321 401051 6162 404477
2362 401071 6204 404528
2403 401091 6246 404579
2444 401111 6288 404630
2485 401131 6330 404681
2526 401151 6372 404732
2567 401171 6414 404783
2608 401191 6456 404834
2649 401211 6498 404885
2690 401231 6540 404936
2731 401251 6582 404987
2772 401271 6624 405038
2813 401291 6666 405089
2854 401311 6708 405140
2895 401331 6750 405191
2936 401351 6792 405242
2977 401371 6834 405293
3018 401391 6876 405344
3059 401411 6918 405395
3100 401431 6960 405446
3141 401451 7002 405497
3182 401471 7044 405548
3223 401491 7086 405599
3264 401511 7128 405650
3305 401531 7170 405701
3346 401551 7212 405752
3387 401571 7254 405803
3428 401591 7296 405854
3469 401611 7338 405905
3510 401631 7380 405956
3551 401651 7422 406007
3592 401671 7464 406058
3633 401691 7506 406109
3674 401711 7548 406160
3715 401731 7590 406211
3756 401751 7632 406262
3797 401771 7674 406313
3838 401791 7716 406364
3879 401811 7758 406415
3920 401831 7800 406466
3961 401851 7842 406517
4002 401871 7884 406568
4043 401891 7926 406619
4084 401911 7968 406670
4125 401931 8010 406721
4166 401951 8052 406772
4207 401971 8094 406823
4248 401991 8136 406874
4289 402011 8178 406925
6
400 401111
3919 402000
2410 403067
2030 3045
3788 401822
2 2
10
32838 98856 169286 382575
17392 71651 438235 271602
17756 88860 728073 750123
43610 2652 198644 200461
31939 40939 546682 463968
53143 78026 93024 23071
54934 9741 105633 937737
11185 90282 729807 417870
59341 28361 118511 176613
69330 15347 51419 29368
3
235663 122222
111111 111000
99199 88888
100
0 0 100000 100000
0 100000 100000 100000
0 200000 100000 100000
0 300000 100000 100000
0 400000 100000 100000
0 500000 100000 100000
0 600000 100000 100000
0 700000 100000 100000
0 800000 100000 100000
0 900000 100000 100000
100000 0 100000 100000
100000 100000 100000 100000
100000 200000 100000 100000
100000 300000 100000 100000
100000 400000 100000 100000
100000 500000 100000 100000
100000 600000 100000 100000
100000 700000 100000 100000
100000 800000 100000 100000
100000 900000 100000 100000
200000 0 100000 100000
200000 100000 100000 100000
200000 200000 100000 100000
200000 300000 100000 100000
200000 400000 100000 100000
200000 500000 100000 100000
200000 600000 100000 100000
200000 700000 100000 100000
200000 800000 100000 100000
200000 900000 100000 100000
300000 0 100000 100000
300000 100000 100000 100000
300000 200000 100000 100000
300000 300000 100000 100000
300000 400000 100000 100000
300000 500000 100000 100000
300000 600000 100000 100000
300000 700000 100000 100000
300000 800000 100000 100000
300000 900000 100000 100000
400000 0 100000 100000
400000 100000 100000 100000
400000 200000 100000 100000
400000 300000 100000 100000
400000 400000 100000 100000
400000 500000 100000 100000
400000 600000 100000 100000
400000 700000 100000 100000
400000 800000 100000 100000
400000 900000 100000 100000
500000 0 100000 100000
500000 100000 100000 100000
500000 200000 100000 100000
500000 300000 100000 100000
500000 400000 100000 100000
500000 500000 100000 100000
500000 600000 100000 100000
500000 700000 100000 100000
500000 800000 100000 100000
500000 900000 100000 100000
600000 0 100000 100000
600000 100000 100000 100000
600000 200000 100000 100000
600000 300000 100000 100000
600000 400000 100000 100000
600000 500000 100000 100000
600000 600000 100000 100000
600000 700000 100000 100000
600000 800000 100000 100000
600000 900000 100000 100000
700000 0 100000 100000
700000 100000 100000 100000
700000 200000 100000 100000
700000 300000 100000 100000
700000 400000 100000 100000
700000 500000 100000 100000
700000 600000 100000 100000
700000 700000 100000 100000
700000 800000 100000 100000
700000 900000 100000 100000
800000 0 100000 100000
800000 100000 100000 100000
800000 200000 100000 100000
800000 300000 100000 100000
800000 400000 100000 100000
800000 500000 100000 100000
800000 600000 100000 100000
800000 700000 100000 100000
800000 800000 100000 100000
800000 900000 100000 100000
900000 0 100000 100000
900000 100000 100000 100000
900000 200000 100000 100000
900000 300000 100000 100000
900000 400000 100000 100000
900000 500000 100000 100000
900000 600000 100000 100000
900000 700000 100000 100000
900000 800000 100000 100000
900000 900000 100000 100000
10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
999999 999999
200 23040
12212 230230
928736 773600
4
100 100 100 100
201 201 100 100
100 201 100 100
201 100 100 100
1
200 200
100
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
300 300 10000 10000
2
5000 5000
10300 10300
0