CF2258D.Magic Tiles

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.

《魔法瓷砖》（Magic Tiles）是一款全球知名的钢琴游戏，本题即基于该游戏设计。诺扬（Noyan）不擅长需要快速反应与高度专注力的游戏，因此他只能使用一根手指操作，即每行最多按下一块瓷砖。此外，若他在同一列中连续按下瓷砖，则可获得与连续次数（即连击长度）相关的分数；但若按下了错误的瓷砖，他将立即被淘汰。请帮助诺扬确定最优操作方案，以最大化其总得分。

给定一个具有 $10^{18}$ 行、$2$ 列的网格。行编号从 $1$ 到 $10^{18}$，列编号为 $1$ 和 $2$。每个格子被染成白色或黑色。

你需要选出若干黑色格子构成一个子集，满足：每行至多选一个格子。目标是最大化总得分 $S$，该总得分等于第一列与第二列各自得分之和。

单列的得分定义为

$$\sum_{i=1}^{k} 100^{100^{x_i}},$$

其中 $k$ 是该列中所选格子形成的极大连续段的数量，$x_i$ 表示第 $i$ 个连续段的长度。

请计算所能获得的最大总得分。

由于网格规模极其庞大（达 $10^{18}$ 行），输入将以压缩格式给出：对每一列，仅提供该列中所有极大黑色连续段的信息。输出也需采用压缩格式。具体细节请参见输入与输出说明部分。

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$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 3000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3000$），分别表示第 1 列和第 2 列中黑色格子段的数量。

每个测试用例的接下来 $n$ 行描述第 1 列中的黑色格子段。其中第 $i$ 行包含两个整数 $l_{1, i}$ 和 $r_{1, i}$（$1 \le l_{1, i} \le r_{1, i} \le 10^{18}$），表示从第 $l_{1, i}$ 行到第 $r_{1, i}$ 行（含端点）的一段连续黑色格子。

每个测试用例的再接下来 $m$ 行描述第 2 列中的黑色格子段。其中第 $j$ 行包含两个整数 $l_{2, j}$ 和 $r_{2, j}$（$1 \le l_{2, j} \le r_{2, j} \le 10^{18}$），表示从第 $l_{2, j}$ 行到第 $r_{2, j}$ 行（含端点）的一段连续黑色格子。

在同一列内，任意两个给定的段互不接触。更准确地说，对所有合法的 $i$ 和 $j$，均有 $r_{1, i} + 1 \lt l_{1, i+1}$ 且 $r_{2, j} + 1 \lt l_{2, j+1}$。

保证所有测试用例中 $n$ 的总和不超过 $3000$，且所有测试用例中 $m$ 的总和不超过 $3000$。

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$).

对每个测试用例，输出两行。

第一行应包含一个整数 $c$（$1 \leq c$），表示在两列中选出的所有极大连续段的总数。

第二行应包含 $c$ 个整数 $x_1, x_2, \ldots, x_c$，表示所有被选出的段的长度，按非递增顺序排列（即 $x_1 \ge x_2 \ge \ldots \ge x_c \ge 1$）。

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 example

The table of the second example

The table of the third example

In the diagrams above, red indicates selected cells.

在第一个测试用例中，两条黑色线段互不重叠。我们在第一列中选择第 $1$ 至 $3$ 行，在第二列中选择第 $5$ 至 $6$ 行。这样得到两条长度分别为 $3$ 和 $2$ 的线段。

在第二个测试用例中，两列的第 $1$ 至 $4$ 行均为黑色。由于每行至多只能选择一个单元格，我们从其中任意一列中选出全部四个单元格。这样得到一条长度为 $4$ 的线段。

在第三个测试用例中，一种最优选择方案为：

• 第一列的第 $1$ 和 $2$ 行；
• 第二列的第 $3$ 至 $7$ 行；
• 第一列的第 $8$ 行；
• 第二列的第 $9$ 至 $12$ 行。

因此，第一列中被选中的线段长度分别为 $2$ 和 $1$，第二列中被选中的线段长度分别为 $5$ 和 $4$。将所有线段长度按非递增顺序排序后，答案为 $[5,4,2,1]$。

可以证明，所有给出的构造方案在其各自测试用例中均为最优解。

第一个示例的表格

第二个示例的表格

第三个示例的表格

在上述图示中，红色表示被选中的单元格。