Input
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
Output
3 4