H. Stop the Castle
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ castles and $$$m$$$ obstacles on a chessboard with $$$10^9$$$ rows and $$$10^9$$$ columns. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they're on the same row or the same column, and there are no obstacles or other castles between them. More formally, let $$$(i, j)$$$ be the cell on the $$$i$$$-th row and the $$$j$$$-th column. Two castles positioned at $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ can attack each other, if one of the following conditions is true:

  • $$$i_1 = i_2$$$ and for all $$$\min(j_1, j_2) \lt j \lt \max(j_1, j_2)$$$, there is no obstacle or castle positioned at $$$(i_1, j)$$$.
  • $$$j_1 = j_2$$$ and for all $$$\min(i_1, i_2) \lt i \lt \max(i_1, i_2)$$$, there is no obstacle or castle positioned at $$$(i, j_1)$$$.

Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each other. Note that the additional obstacles cannot be placed in an already occupied cell.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$2 \le n \le 200$$$) indicating the number of castles.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$r_i$$$ and $$$c_i$$$ ($$$1 \le r_i, c_i \le 10^9$$$) indicating that the $$$i$$$-th castle is located on the $$$r_i$$$-th row and the $$$c_i$$$-th column.

The next line contains an integer $$$m$$$ ($$$0 \le m \le 200$$$) indicating the number of obstacles.

For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$r'_i$$$ and $$$c'_i$$$ ($$$1 \le r'_i, c'_i \le 10^9$$$) indicating that the $$$i$$$-th obstacle is located on the $$$r'_i$$$-th row and the $$$c'_i$$$-th column.

It's guaranteed that the occupied cells are distinct. It's also guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ of all test cases will exceed $$$400$$$.

Output

For each test case:

If it is possible to stop the castles from attacking each other, first output one line containing one integer $$$k$$$, indicating the minimum number of additional obstacles needed. Then output $$$k$$$ lines where the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$) separated by a space, indicating that you're going to place the $$$i$$$-th additional obstacle in cell $$$(x_i, y_i)$$$. If there are multiple valid answers, you can output any of them.

If it is impossible to stop the castles from attacking each other, just output -1 in one line.

Example
Input
4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0
Output
2
2 3
4 6
0
1
2 3
-1
Note

The first sample test case is shown below. We only need to add $$$2$$$ additional obstacles (marked as stars), one located at $$$(2, 3)$$$ while the other located at $$$(4, 6)$$$.

For the second sample test case, the only two castles do not lie on the same row or the same column, so no obstacle is needed.