D. Magic Tiles
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Magic Tiles is a well-known piano game worldwide, and this problem is based on it. Noyan is not very good at games that require fast reflexes and high concentration. As a result, he can only use a single finger, meaning he can press at most one tile per row. Furthermore, when he presses the same column consecutively, he earns points proportional to the length of his streak. However, if he presses an incorrect tile, he is eliminated. Help Noyan determine the optimal configuration to maximize his score.

You are given a grid with $$$10^{18}$$$ rows and $$$2$$$ columns. Rows are indexed from $$$1$$$ to $$$10^{18}$$$, and columns are indexed $$$1$$$ and $$$2$$$. Each cell is colored either white or black.

You need to select a subset of black cells such that at most one cell is selected from each row. Your goal is to maximize the total score $$$S$$$, which is the sum of scores calculated for the first and second columns independently.

The score for a single column is defined as $$$$$$ \sum_{i=1}^{k} 100^{100^{x_i}}, $$$$$$ where $$$k$$$ is the number of maximal contiguous segments of selected cells in that column, and $$$x_i$$$ represents the length of the $$$i$$$-th segment.

Determine the largest total score you can get.

Since the grid is astronomically large, the input is given in a compressed format of maximal black segments for each column. You also need to provide the answer in a compressed format. For more details, refer to the input and output sections.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3000$$$) — the number of segments of black cells in Column 1 and Column 2, respectively.

The next $$$n$$$ lines of each test case contain the black cell segments for Column 1. The $$$i$$$-th of these lines contains two integers $$$l_{1, i}$$$ and $$$r_{1, i}$$$ ($$$1 \le l_{1, i} \le r_{1, i} \le 10^{18}$$$), representing a contiguous range of black cells from the $$$l_{1, i}$$$-th to the $$$r_{1, i}$$$-th row, inclusive.

The next $$$m$$$ lines of each test case contain the black cell segments for Column 2. The $$$j$$$-th of these lines contains two integers $$$l_{2, j}$$$ and $$$r_{2, j}$$$ ($$$1 \le l_{2, j} \le r_{2, j} \le 10^{18}$$$), representing a contiguous range of black cells from the $$$l_{2, j}$$$-th to the $$$r_{2, j}$$$-th row, inclusive.

Within the same column, no given segments touch one another. More formally, $$$r_{1, i} + 1 \lt l_{1, i+1}$$$ and $$$r_{2, j} + 1 \lt l_{2, j+1}$$$ for all valid $$$i$$$ and $$$j$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3000$$$, and the sum of $$$m$$$ over all test cases doesn't exceed $$$3000$$$.

Output

For each test case, output two lines.

The first line should contain a single integer $$$c$$$ ($$$1 \leq c$$$) — the total number of maximal contiguous segments selected across both columns.

The second line should contain $$$c$$$ integers $$$x_1, x_2, \ldots, x_c$$$ representing the lengths of all selected segments, sorted in non-increasing order ($$$x_1 \ge x_2 \ge \ldots \ge x_c \ge 1$$$).

Example
Input
4
1 1
1 3
5 6
1 1
1 4
1 4
2 2
1 4
7 10
3 7
9 12
1 1
1 1000000000000000000
1 1
Output
2
3 2 
1
4 
4
5 4 2 1 
1
1000000000000000000
Note

In the first test case, the two black segments do not overlap. We select rows $$$1$$$ through $$$3$$$ in the first column and rows $$$5$$$ through $$$6$$$ in the second column. This produces two segments with lengths $$$3$$$ and $$$2$$$.

In the second test case, both columns are black on rows $$$1$$$ through $$$4$$$. Since at most one cell may be selected from each row, we select all four cells from either one of the columns. This produces a single segment of length $$$4$$$.

In the third test case, one optimal selection is:

  • rows $$$1$$$ and $$$2$$$ in the first column;
  • rows $$$3$$$ through $$$7$$$ in the second column;
  • row $$$8$$$ in the first column;
  • rows $$$9$$$ through $$$12$$$ in the second column.

Therefore, the selected segments in the first column have lengths $$$2$$$ and $$$1$$$, while the selected segments in the second column have lengths $$$5$$$ and $$$4$$$. After sorting all segment lengths in non-increasing order, the answer is $$$[5,4,2,1]$$$.

It can be shown that all given constructions are optimal for their respective test cases.

The table of the first exampleThe table of the second exampleThe table of the third example

In the diagrams above, red indicates selected cells.