Antiamuny 正在管理长度 $$$m$$$ 的一维轨道上的 $$$n$$$ 滑块。每个滑块恰好占据一个空间单位,并从不同的位置开始。滑块的编号从 $$$1$$$ 到 $$$n$$$ 并从左到右排列,因此第 $$$i$$$ 个滑块最初位于位置 $$$a_i$$$。
Antiamuny 被给予 $$$q$$$ 操作。每个操作由两个整数 $$$i$$$ 和 $$$x$$$ ($$$1\le i\le 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, \textbf{4}, \textbf{5}, \textbf{6}]$$$。
不幸的是,Antiamuny 忘记了 $$$q$$$ 操作的应用顺序。为了恢复结果,他决定独立模拟每个 $$$q!$$$ 可能的操作排列。对于长度为 $$$q$$$$$^{\text{∗}}$$$ 的每个排列 $$$p$$$,将 $$$f_i(p)$$$ 定义为按 $$$p$$$ 指定的顺序应用操作后第 $$$i$$$ 个滑块的最终位置。
也就是说,从$$$a_1、a_2、\ldots、a_n$$$的初始位置开始,Antiamuny首先应用第$$$p_1$$$操作,然后应用第$$$p_2$$$操作,依此类推,直到第$$$p_q$$$操作。 $$$f_i(p)$$$ 的值是该操作序列末尾的第 $$$i$$$ 滑块的位置。
您的任务是计算每个滑块 $$$i$$$ ($$$1\le i\le n$$$) 的所有 $$$q!$$$ 操作排列 $$$p$$$ 上 $$$f_i(p)$$$ 的总和。由于结果可能很大,因此输出每个和模 $$$10^9 + 7$$$。
$$$^{\text{*}}$$$长度$$$q$$$的排列是一个由从$$$1$$$到$$$q$$$以任意顺序的$$$q$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$q=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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, \ldots, a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq m$$$) - 每个滑块的初始位置。
接下来的 $$$q$$$ 行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$, $$$i \leq x \leq m - n + i$$$) - 分别是要移动的滑块的索引和要将滑块移动到的位置。
保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$5\cdot 10^3$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 表示操作的所有 $$$q!$$$ 排列 $$$p$$$ 上 $$$f_i(p)$$$ 的总和,模 $$$10^9 + 7$$$。
示例
输入复制
35 10 31 3 5 7 95 62 61 45 10 52 3 5 7 91 64 73 35 74 93 1000000000 31 10 2537463923 1000000003 10000000003 500000000
输出复制
18 29 35 41 47 340 460 580 930 1090 6 60 199999979
注意
在第一个测试用例中:
- 如果操作按照 $$$[2,1,3]$$$ 的顺序完成,我们首先应用第二个操作,将 $$$2$$$-nd 滑块移动到位置 $$$6$$$;然后应用第一个操作,将第 $$$5$$$ 滑块移动到位置 $$$6$$$;最后应用第三个操作,将 $$$1$$$-st 滑块移动到位置 $$$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$$$,$$$6$$$不同场景的位置总和为$$$5+6+6+3+6+3=29$$$。
对于滑块$$$3$$$,$$$6$$$不同场景的位置总和为$$$6+7+7+4+7+4=35$$$。
对于滑块$$$4$$$,$$$6$$$不同场景的位置总和为$$$7+8+8+5+8+5=41$$$。
对于滑块 $$$5$$$,$$$6$$$ 不同场景的位置总和为 $$$8+9+9+6+9+6=47$$$。