Input 
3
2 1
1 2
4 2
1 2 2 2
11 3
5 5 5 1 5 5 1 5 5 5 1
Output 
1 2
1 2
2 2
1 3
4 4
5 5
1 1
2 2
3 11