2 5
1 4 1000
5 4 1000
1 5 3 5 3 3 5 3 5 1 1 1
3 2
0 0 1000
6 0 600
6 6 1000
1 1 5 5 5 2
3 2
0 0 1000
6 0 300
6 6 1000
2 2 5 5 5 2
5 4
0 2 500
7 10 2000
7 6 2000
11 6 2000
4 3 200
1 1 3 8 9 8 9 1 5 3
5 4
0 2 500
7 6 2000
7 10 2000
11 6 2000
4 3 200
1 1 3 8 9 8 9 1 5 3
6 5
4 1 1000000
8 13 100000
18 1 1000000
10 13 100000
5 25 100000
23 23 40000
0 0 4 25 9 0 9 25 25 25 25 0
2 10
2 1 888192
11 13 884096
0 0 0 15 15 15 15 0 3 0 3 11 11 11 11 4 6 4 6 8 9 8
1 10
11 13 884096
0 0 0 15 15 15 15 0 3 0 3 11 11 11 11 4 6 4 6 8 9 8
2 1
5 10 1000
5 4 24000
0 0 5 9
10 1
4 8 2000
13 9 1000
0 2 1000
20 23 2000
37 33 1000
53 57 3000
98 100 500
69 66 2000
81 89 2000
97 94 1000
0 0 100 100
0