D. Антиамуни и движения ползунков
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антиамуни управляет $$$n$$$ ползунками на одномерной дорожке длиной $$$m$$$. Каждый ползунок занимает ровно одну единицу пространства и начинается с уникальной позиции. Ползунки пронумерованы от $$$1$$$ до $$$n$$$ и расположены слева направо, так что $$$i$$$-й ползунок изначально находится на позиции $$$a_i$$$.

Антиамуни даны $$$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}]$$$.

К сожалению, Антиамуни забыл порядок, в котором были применены $$$q$$$ операций. Чтобы восстановить результаты, он решает независимо смоделировать каждую из $$$q!$$$ возможных перестановок операций. Для каждой перестановки $$$p$$$ длины $$$q$$$$$$^{\text{∗}}$$$, определим $$$f_i(p)$$$ как конечную позицию $$$i$$$-го ползунка после применения операций в порядке $$$p$$$.

Другими словами, начиная с начальных позиций $$$a_1, a_2, \ldots, a_n$$$, Антиамуни сначала применяет $$$p_1$$$-ю операцию, затем $$$p_2$$$-ю операцию и так далее, пока не дойдет до $$$p_q$$$-й операции. Значение $$$f_i(p)$$$ — это позиция $$$i$$$-го ползунка в конце этой последовательности операций.

Ваша задача — вычислить для каждого ползунка $$$i$$$ ($$$1\le i\le n$$$) сумму $$$f_i(p)$$$ по всем $$$q!$$$ перестановкам $$$p$$$ операций. Поскольку результат может быть большим, выводите каждую сумму по модулю $$$10^9 + 7$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$q$$$ является массив, состоящий из $$$q$$$ различных целых чисел от $$$1$$$ до $$$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$$$-е число представляет сумму $$$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$$$ сумма позиций $$$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$$$.