**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**
Чтобы отпраздновать начало весны, \(N\) коров фермера Джона (\(1 \leq N \leq 2 \cdot 10^5\)) придумали новый интригующий танец, в котором они встают в круг и перестраиваются предсказуемыv способом.
В частности, по кругу есть \(N\) позиций, пронумерованные последовательно от \(0\) до \(N-1\), причем позиция \(0\) следует за позицией \(N-1\). На каждой позиции находится корова. Коровы также последовательно нумеруются от \(0\) до \(N-1\). Изначально корова \(i\) находится в позиции \(i\). Вам сообщают набор из \(K\) позиций \(0=A_1<A_2< \ldots< A_K<N\), которые являются «активными», что означает, что коровы в этих позициях будут двигаться следующими (\(1 \leq K \leq N\)).
В каждую минуту танца происходят две вещи. Во-первых, коровы в активных позициях меняются: корова в позиции \(A_1\) перемещается в позицию \(A_2\), корова в позиции \(A_2\) перемещается в позицию \(A_3\) и так далее, с коровой в позиции \(A_K\) переход на позицию \(A_1\). Все эти \(K\) перемещения происходят одновременно, поэтому после завершения вращения все активные позиции по-прежнему содержат ровно одну корову. Далее смещаются сами активные позиции:
\(A_1\) становится \(A_1+1\), \(A_2\) становится \(A_2+1\) и так далее (если \(A_i = N-1\) для некоторой активной позиции, то \(A_i\) возвращается к \(0\)).
Рассчитайте порядок коров после \(T\) минут танца (\(1\le T\le 10^9\)).
ФОРМАТ ВВОДА (с терминала/стандартного ввода):
Первая строка содержит три целых числа
\(N\),
\(K\) и
\(T\).
Вторая строка содержит \(K\) целых чисел, представляющих исходный набор активных позиций.
\(A_1,A_2, \ldots A_K\). Напомним, что \(A_1 = 0\) и что они даны в порядке возрастания.
ФОРМАТ ВЫВОДА (на терминал / стандартный вывод):
Выведите порядок коров через \(T\) минут, начиная с коровы в позиции \(0\), разделенных одиночными пробелами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 4
0 2 3
|
1 2 3 4 0
|