6
5 2
2 2 2
1 1 1
5 3 2
4 4 1
6 4 2
5 2
1 2 1
2 2 2
2 4 1
2 3 2
3 3 2
5 2
5 4 2
5 3 1
2 4 2
3 3 1
4 4 2
9 3
2 4 2
3 4 1
5 5 2
5 4 3
6 3 2
5 2 1
4 5 2
6 4 2
4 4 3
2 2
1000000000 1 1
1000000000 1000000000 2
2 2
1 1000000000 2
1000000000 1000000000 1