F. Antiamuny 与滑块移动

时间限制： 每测试 $5$ 秒
内存限制： 每测试 $512$ 兆字节

Antiamuny 正在管理一条长度为 $m$ 的一维轨道上的 $n$ 个滑块。每个滑块恰好占据一个单位空间，并且初始时位于不同的位置。滑块编号从 $1$ 到 $n$，从左到右排列，因此第 $i$ 个滑块初始位于位置 $a_i$。

Antiamuny 被给定 $q$ 个操作。每个操作由两个整数 $i$ 和 $x$ $(1 \leq i \leq n,\ i \leq x \leq m - n + i)$ 描述。该操作将第 $i$ 个滑块移动到位置 $x$。然而，如果此移动导致与另一个滑块发生碰撞（即，如果第 $i$ 个滑块的当前位置与目的地 $x$ 之间存在任何其他滑块），则该阻碍滑块会沿相同方向被推动一个单位，直到不再与第 $i$ 个滑块发生碰撞。这可能引发连锁反应，其中一个滑块推动另一个滑块，依此类推，直到所有滑块再次占据不同的位置。

重要的是，注意操作不会改变滑块的相对顺序：左侧第 $i$ 个滑块将始终保持为左侧第 $i$ 个滑块。此外，对 $x$ 的约束确保所有滑块始终保持在轨道上，位置介于 $1$ 和 $m$ 之间。

例如，假设初始滑块位置为 $[1, 3, 5, 7, 9]$。如果将第五个滑块（位于位置 $9$）移动到位置 $6$，它将推动第四个滑块从 $7$ 到 $5$，这又推动第三个滑块从 $5$ 到 $4$。最终位置变为 $[1, 3, 4, 5, 6]$。

不幸的是，Antiamuny 忘记了这 $q$ 个操作的执行顺序。为了恢复结果，他决定独立模拟所有 $q!$ 种可能的操作排列。对于每个长度为 $q$ 的排列 $p$，定义 $f_i(p)$ 为按照 $p$ 指定的顺序执行操作后第 $i$ 个滑块的最终位置。

换句话说，从初始位置 $a_1, a_2, \dots, a_n$ 开始，Antiamuny 首先执行第 $p_1$ 个操作，然后执行第 $p_2$ 个操作，依此类推，直到第 $p_q$ 个操作。$f_i(p)$ 的值是该操作序列结束时第 $i$ 个滑块的位置。

你的任务是：对于每个滑块 $i$ $(1 \leq i \leq n)$，计算 $f_i(p)$ 在所有 $q!$ 个排列 $p$ 上的总和。由于结果可能很大，对每个总和输出模 $10^9 + 7$ 的结果。

---

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \leq t \leq 10^3)$。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m, q$ $(1 \leq n, q \leq 5 \cdot 10^3,\ n \leq m \leq 10^9)$ — 分别表示滑块数量、轨道长度和操作数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_1 < a_2 < \dots < a_n \leq m)$ — 每个滑块的初始位置。

接下来 $q$ 行，每行包含两个整数 $i$ 和 $x$ $(1 \leq i \leq n,\ i \leq x \leq m - n + i)$ — 分别表示要移动的滑块索引以及滑块要移动到的位置。

保证所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $5 \cdot 10^3$。

---

输出格式

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示 $f_i(p)$ 在所有 $q!$ 个排列 $p$ 上的总和，对 $10^9 + 7$ 取模。

---

样例

输入

3
5 10 3
1 3 5 7 9
5 6
2 6
1 4
5 10 5
2 3 5 7 9
1 6
4 7
3 3
5 7
4 9
3 1000000000 3
1 10 253746392
3 100000000
3 1000000000
3 500000000

输出

18 29 35 41 47 
340 460 580 930 1090 
6 60 199999979 

---

样例解释

在第一个测试用例中：

• 如果操作按顺序 $[2, 1, 3]$ 执行：先执行第二个操作（将第 $2$ 个滑块移动到位置 $6$）；然后执行第一个操作（将第 $5$ 个滑块移动到位置 $6$）；最后执行第三个操作（将第 $1$ 个滑块移动到位置 $4$）。最终滑块位置为 $[4, 5, 6, 7, 8]$。

• 如果操作按顺序 $[1, 2, 3]$ 执行：最终滑块位置为 $[4, 6, 7, 8, 9]$。

• 如果操作按顺序 $[1, 3, 2]$ 执行：最终滑块位置为 $[4, 6, 7, 8, 9]$。

• 如果操作按顺序 $[2, 3, 1]$ 执行：最终滑块位置为 $[2, 3, 4, 5, 6]$。

• 如果操作按顺序 $[3, 1, 2]$ 执行：最终滑块位置为 $[2, 6, 7, 8, 9]$。

• 如果操作按顺序 $[3, 2, 1]$ 执行：最终滑块位置为 $[2, 3, 4, 5, 6]$。

对于滑块 $1$，$6$ 种不同情况下的位置总和为：

$$4 + 4 + 4 + 2 + 2 + 2 = 18$$

对于滑块 $2$，总和为：

$$5 + 6 + 6 + 3 + 6 + 3 = 29$$

对于滑块 $3$，总和为：

$$6 + 7 + 7 + 4 + 7 + 4 = 35$$

对于滑块 $4$，总和为：

$$7 + 8 + 8 + 5 + 8 + 5 = 41$$

对于滑块 $5$，总和为：

$$8 + 9 + 9 + 6 + 9 + 6 = 47$$