题目描述

安蒂亚穆尼在一条长度为 $m$ 的一维轨道上操控 $n$ 个滑块。 每个滑块占用恰好 $1$ 个单位位置，初始所有滑块位置互不相同。 滑块编号为 $1 \sim n$，按从左至右顺序排列，第 $i$ 个滑块初始位置为 $a_i$。

给定 $q$ 次操作，每次操作给出两个整数 $i,x$（$1\le i\le n,\ i\le x\le m-n+i$）： 将第 $i$ 个滑块移动到位置 $x$。

移动规则： 若本次移动与其他滑块发生碰撞（滑块当前位置与目标位置之间存在其他滑块）， 被阻挡的滑块会被同向推动 $1$ 个单位； 该挤压会产生连锁反应，连续推动后续滑块，直到所有滑块位置互不重叠。

重要性质： 所有操作不会改变滑块的相对左右次序； 原本左数第 $i$ 个滑块，操作后仍然是左数第 $i$ 个。 同时题目对 $x$ 的范围限制，保证所有滑块始终合法停留在轨道 $[1,m]$ 范围内。

举例说明

初始滑块位置：$[1,3,5,7,9]$ 将第 $5$ 个滑块移动到位置 $6$：

• 挤压第 $4$ 个滑块：$7 \to 5$
• 连锁挤压第 $3$ 个滑块：$5 \to 4$ 最终滑块位置：$[1,3,4,5,6]$。

---

现已知全部 $q$ 条操作，但操作执行顺序未知。 需要考虑 $q!$ 种操作的全排列执行顺序： 对于长度为 $q$ 的任意操作排列 $p$， 从初始位置 $a_1,a_2,\dots,a_n$ 开始，依次执行 $p_1,p_2,\dots,p_q$。

定义： $f_i(p)$：以排列 $p$ 的顺序执行所有操作后，第 $i$ 个滑块的最终位置。

你的任务： 对每个滑块 $i$，求出所有 $q!$ 种排列下 $f_i(p)$ 的总和； 答案对 $\boldsymbol{10^9+7}$ 取模。

---

补充定义

长度为 $q$ 的排列：由 $1 \sim q$ 全部整数各出现一次构成的序列。

---

输入格式

多组测试数据。 第一行输入测试组数 $t$（$1\le t\le 10^3$）。

每组测试数据：

1. 第一行三个整数 $n,m,q$ $1\le n,q\le 5\times 10^3,\ n\le m\le 10^9$ 依次表示：滑块数量、轨道总长、操作次数。
2. 第二行 $n$ 个严格递增整数 $a_1,a_2,\dots,a_n$ $1\le a_1<a_2<\dots<a_n\le m$，代表各滑块初始位置。
3. 接下来 $q$ 行，每行两个整数 $i,x$，代表一次移动操作。

数据约束： 所有测试数据的 $\boldsymbol{\sum n \le 5\times 10^3}$，$\boldsymbol{\sum q \le 5\times 10^3}$。

---

输出格式

每组测试数据输出 $n$ 个整数， 第 $i$ 个数表示第 $i$ 个滑块在全部排列下的位置总和，对 $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 

---

样例说明（第一组）

$q=3$，总共有 $3! = 6$ 种操作排列。 以一号滑块为例： 六种排列最终位置：$4,4,4,2,2,2$ 求和：

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

其余滑块求和规则一致。