子序列

Problem Description

给出一个长度为 $k$ 的序列 $t$。 现在有 $m$ 种数字，分别为 $1 \sim m$，同时有一个频度序列 $c_1, c_2, \cdots, c_m$，表示数字 $i$ 的出现次数为 $c_i$。 你需要构造一个长度为 $n = \sum c_i$ 的序列 $s$，满足：

• 对于所有 $1 \leq i \leq m$，数字 $i$ 的出现次数为 $c_i$。
• 满足上述条件的情况下。设 $t$ 的极长相同连续段的数量为 $x$，$t$ 中出现的数字种类为 $y$。要求 $s$ 的极长相同连续段数小于等于 $x + m - y$。
• 满足上述条件的情况下。要求序列 $s$ 含有子序列 $t$ 的数量最多。
• 满足上述条件的情况下。要求 $s$ 的字典序最小。 $\dagger$ 子序列：如果 $S'$ 可以通过 $S$ 删除若干个（可能是零个或全部）元素，且不改变剩余元素的相对顺序得到，则称 $S'$ 是 $S$ 的子序列。 $\dagger$ 字典序：当且仅当以下条件之一成立时，序列 $x$ 的字典序小于序列 $y$
• $x$ 是 $y$ 的前缀，但 $x \neq y$。
• 在 $x$ 与 $y$ 不同的第一个位置，序列 $x$ 中的元素小于序列 $y$ 中的元素。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 10^6)$，表示数据组数。对于每组测试数据： 第一行一个正整数 $m, k(1 \leq m \leq 10^5, 1 \leq k \leq 10^5)$，分别表示数字的范围和序列 $t$ 的长度。 第二行 $k$ 个正整数 $t_1, t_2, \cdots, t_k(1 \leq t_i \leq m)$，表示序列 $t$。 第三行 $m$ 个整数 $c_1, c_2, \cdots, c_m(0 \leq c_i \leq 10^6)$，表示每个数字在 $s$ 中的出现次数。 保证所有测试数据中 $m$ 之和与 $k$ 之和均不超过 $1.2 \times 10^5$，$n = \sum c_i$ 之和不超过 $10^6$。

Output

对于每组测试数据：你需要以连续段的形式给出序列 $s$，具体地： 第一行一个正整数 $L$，表示 $s$ 相同数字的连续段个数。 接下来 $L$ 行，从左到右地给出连续段。每行两个用空格隔开的正整数 $a, b$，表示有 $a$ 个数字 $b$ 构成一个连续段。 显然，相邻连续段的数字不能相同。

Sample Input

1
5 4
2 3 4 5
2 2 2 2 2

Sample Output

5
2 1
2 2
2 3
2 4
2 5

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）