3
10 10  20 20
11 11
10 30  20 40
15 35
9
1 2 1 2 1 2 1 2 1
7 1 2 1 2 1 2 1 2
10 45  15 15 
15 45  10 21
20 45  15 21
10 50  20 21
15 50  10 26
20 50  15 26
10 55  20 26
15 55  5  5
20 55  25 25
1000 1000 2000 2000
1500 1500
3000 3000 4000 4000
3500 3500
5
20 20 20 20 20
10 20 30 40 50
3100 3100 1100 1100
3200 3200 1200 1200
3300 3300 1300 1300
3400 3400 1400 1400
3500 3500 1500 1500
1 1 3 3
2 2
20 60  50 10
35 45
5
5 4 3 2 1
1 2 3 4 5
19 45 4 4
51 45 1 10
35 9  10 1
35 61 20 1
35 47 30 1