Дан ориентированный граф из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. В каждую вершину входит хотя бы одно ребро. В графе могут быть петли, но нет кратных рёбер. Для каждой вершины $$$v$$$ задано целое число $$$k_v$$$ от $$$1$$$ до количества входящих в неё рёбер.
На каждой вершине записано число. Каждую секунду все числа обновляются следующим образом. Для вершины $$$v$$$ выписывают числа, находившиеся в вершинах $$$u$$$, для которых существует ребро $$$u\to v$$$, сортируют их в порядке неубывания и записывают в $$$v$$$ число на позиции $$$k_v$$$. Позиции чисел в отсортированном списке нумеруются с $$$1$$$. Иными словами, новое число на вершине $$$v$$$ — $$$k_v$$$-я порядковая статистика массива, состоящего из чисел на таких вершинах $$$u$$$, для которых существует ребро $$$u \to v$$$.
Все вершины обновляются одновременно: при вычислении новых чисел используются только числа до начала текущего обновления. Если в вершине есть петля, число, записанное на ней, также участвует в выборе.
Надо обработать $$$q$$$ запросов следующего формата:
В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1\le n\le20$$$; $$$n\le m\le n^2$$$; $$$1\le q\le10^5$$$) — количество вершин, рёбер и запросов.
Во второй строке даны $$$n$$$ целых чисел $$$k_1,k_2,\ldots,k_n$$$. Для каждой вершины $$$v$$$ выполняется $$$1\le k_v\le d_v$$$, где $$$d_v$$$ — количество входящих в неё рёбер.
В следующих $$$m$$$ строках даны по два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u,v\le n$$$), обозначающих ребро из $$$u$$$ в $$$v$$$. Все упорядоченные пары $$$(u,v)$$$ различны.
Каждая из следующих $$$q$$$ строк содержит $$$n+1$$$ целое число $$$t,a_1,a_2,\ldots,a_n$$$ ($$$0\le t\le10^{18}$$$; $$$1\le a_i\le10^9$$$) — параметры очередного запроса.
На каждый запрос выведите $$$n$$$ целых чисел — значения на вершинах $$$1,2,\dots,n$$$ через $$$t$$$ секунд.
3 3 41 1 11 22 33 10 4 8 151 4 8 152 4 8 151000000000000000000 1 2 3
4 8 15 15 4 8 8 15 4 3 1 2
2 4 31 21 11 22 12 21 10 11000000000000000000 7 70 1000000000 1
1 10 7 7 1000000000 1
4 8 41 2 2 11 12 11 22 23 22 34 33 41 8 3 5 12 8 3 5 13 8 3 5 11000000000000000000 8 3 5 1
3 5 3 5 3 3 5 3 3 3 3 5 3 3 5 3
В первом примере каждое число переходит в следующую вершину цикла. Через три секунды все числа возвращаются на исходные места.
Во втором примере первая вершина выбирает минимум из двух чисел, а вторая — максимум.
В третьем примере из массива $$$[8,3,5,1]$$$ после первого обновления получается $$$[3,5,3,5]$$$, а после второго — $$$[3,3,5,3]$$$.
