Прогуливаясь мимо прилавков с фермерскими продуктами, Busy Beaver обратил внимание на местного молочника, у которого на прилавке была необычная настольная игра.

На столе находится круговое поле с $N$ клетками, пронумерованными от $0$ до $N - 1$. Busy Beaver играет в игру на этом поле с помощью $N$-гранного кубика, грани которого пронумерованы от $0$ до $N - 1$. Если он находится на клетке $s$ и делает ход на $t$ шагов, он перемещается непосредственно на клетку $s + t \pmod N$.

На поле также есть один магический портал: если игрок оказывается ровно на клетке $X$, он мгновенно телепортируется на клетку $Y$.

Busy Beaver бросает кубик $K$ раз и получает последовательность $a_1, a_2, \dots, a_K$. Начиная с некоторой начальной клетки, Busy Beaver перемещается на $a_1$ шагов, затем на $a_2$ шагов и так далее, пока не выполнит все $K$ ходов, где на $i$-м ходу он перемещается на $a_i$ шагов.

Для каждой возможной начальной клетки от $0$ до $N - 1$ (включительно, за исключением клетки $X$) определите клетку, на которой окажется Busy Beaver после завершения всех $K$ ходов (с учетом всех телепортаций).

Входные данные

Первая строка содержит количество тестов $T$ ($1 \le T \le 2 \cdot 10^3$).

Первая строка каждого теста содержит четыре целых числа $N, K, X$ и $Y$ ($2 \le N \le 5 \cdot 10^5, 1 \le K \le 5 \cdot 10^5, 0 \le X, Y < N, X \neq Y$).

Вторая строка каждого теста содержит $K$ целых чисел $a_1, a_2, \dots, a_K$ ($0 \le a_i < N$).

Сумма $N$ по всем тестам не превышает $5 \cdot 10^5$. Сумма $K$ по всем тестам не превышает $5 \cdot 10^5$.

Выходные данные

Для каждого теста выведите $N - 1$ целое число, представляющее клетку, на которой окажется Busy Beaver, если он начал с клетки $i$, для всех $0 \le i < N$, кроме $i = X$.

Оценка

• (20 баллов): Сумма $N$ по всем тестам не превышает $5 \cdot 10^3$, и сумма $K$ по всем тестам не превышает $5 \cdot 10^3$.
• (80 баллов): Дополнительных ограничений нет.

Примеры

Входные данные 1

3
5 1 0 1
1
5 3 0 1
1 2 3
20 10 3 1
4 15 9 2 6 5 3 5 8 9

Выходные данные 1

2 3 4 1
2 4 4 1
6 7 6 6 11 10 11 14 15 16 17 18 17 18 17 2 1 4 1

Примечание

В первом примере $N=5$ клеток и один бросок кубика, выпало 1. Портал телепортирует игрока из клетки $0$ в клетку $1$. Для каждой начальной клетки последовательность событий такова:

• $0$: Портал телепортирует из этой клетки; выводить ничего не нужно.
• $1$: начинает на клетке $1$, перемещается на $1$ шаг в клетку $2$.
• $2$: начинает на клетке $2$, перемещается на $1$ шаг в клетку $3$.
• $3$: начинает на клетке $3$, перемещается на $1$ шаг в клетку $4$.
• $4$: начинает на клетке $4$, перемещается на $1$ шаг в клетку $0$ и телепортируется в клетку $1$.

Во втором примере $N=5$ клеток и три броска кубика: $1, 2, 3$. Портал телепортирует игрока из клетки $0$ в клетку $1$. Для каждой начальной клетки последовательность событий такова:

• $0$: Портал телепортирует из этой клетки; выводить ничего не нужно.
• $1$: начинает на клетке $1$, перемещается на $1$ шаг в клетку $2$, на $2$ шага в клетку $4$, на $3$ шага в клетку $2$.
• $2$: начинает на клетке $2$, перемещается на $1$ шаг в клетку $3$, на $2$ шага в клетку $0$ и телепортируется в клетку $1$, на $3$ шага в клетку $4$.
• $3$: начинает на клетке $3$, перемещается на $1$ шаг в клетку $4$, на $2$ шага в клетку $1$, на $3$ шага в клетку $4$.
• $4$: начинает на клетке $4$, перемещается на $1$ шаг в клетку $0$ и телепортируется в клетку $1$, на $2$ шага в клетку $3$, на $3$ шага в клетку $1$.