Przechadzając się obok świeżych produktów, Busy Beaver zwraca uwagę na lokalnego sprzedawcę nabiału z osobliwą grą planszową na swoim stoisku.

Na planszy znajduje się $N$ pól ponumerowanych od $0$ do $N - 1$. Busy Beaver gra w grę na tej planszy za pomocą $N$-ściennej kostki oznaczonej liczbami od $0$ do $N - 1$. Jeśli znajduje się na polu $s$ i wykona ruch o $t$ kroków, wyląduje bezpośrednio na polu $s + t \pmod N$.

Na planszy znajduje się również jeden magiczny portal, taki że jeśli gracz wyląduje dokładnie na polu $X$, zostaje natychmiast przeniesiony na pole $Y$.

Busy Beaver rzuca kostką $K$ razy i otrzymuje sekwencję $a_1, a_2, \dots, a_K$. Z pola początkowego Busy Beaver wykona ruch o $a_1$ kroków, następnie o $a_2$ kroków i tak dalej, aż wykona wszystkie $K$ ruchów, gdzie w $i$-tym ruchu przesuwa się o $a_i$ kroków.

Dla każdego możliwego pola początkowego od $0$ do $N - 1$ (włącznie, z wyłączeniem pola $X$), określ pole, na którym Busy Beaver wyląduje po zakończeniu wszystkich $K$ ruchów (uwzględniając wszelkie teleportacje).

Wejście

Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 2 \cdot 10^3$).

Pierwsza linia każdego zestawu danych zawiera cztery liczby całkowite $N, K, X$ oraz $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$).

Druga linia każdego zestawu danych zawiera $K$ liczb całkowitych $a_1, a_2, \dots, a_K$ ($0 \le a_i < N$).

Suma $N$ we wszystkich zestawach danych nie przekracza $5 \cdot 10^5$.

Suma $K$ we wszystkich zestawach danych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wypisz $N - 1$ liczb całkowitych reprezentujących pole, na którym Busy Beaver wylądowałby, gdyby rozpoczął grę na polu $i$, dla wszystkich $0 \le i < N$ z wyłączeniem $i = X$.

Podzadania

Istnieją dwa podzadania dla tego problemu:

• (20 punktów): Suma $N$ we wszystkich zestawach danych nie przekracza $5 \cdot 10^3$, a suma $K$ we wszystkich zestawach danych nie przekracza $5 \cdot 10^3$.
• (80 punktów): Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 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

Uwagi

W pierwszym przykładowym zestawie danych na planszy znajduje się 5 pól, a rzut kostką daje wynik 1. Portal teleportuje gracza z pola 0 na pole 1. Dla każdego z pól startowych, oto sekwencja zdarzeń:

• 0: Portal teleportuje z tego pola; nie musimy nic wypisywać.
• 1: start na polu 1, ruch o 1 na pole 2
• 2: start na polu 2, ruch o 1 na pole 3
• 3: start na polu 3, ruch o 1 na pole 4
• 4: start na polu 4, ruch o 1 na pole 0 i teleportacja na pole 1

W drugim przykładowym zestawie danych na planszy znajduje się 5 pól, a trzy rzuty kostką dają odpowiednio 1, 2, 3. Portal teleportuje gracza z pola 0 na pole 1. Dla każdego z pól startowych, oto sekwencja zdarzeń:

• 0: Portal teleportuje z tego pola; nie musimy nic wypisywać.
• 1: start na polu 1, ruch o 1 na pole 2, ruch o 2 na pole 4, ruch o 3 na pole 2
• 2: start na polu 2, ruch o 1 na pole 3, ruch o 2 na pole 0 i teleportacja na pole 1, ruch o 3 na pole 4
• 3: start na polu 3, ruch o 1 na pole 4, ruch o 2 na pole 1, ruch o 3 na pole 4
• 4: start na polu 4, ruch o 1 na pole 0 i teleportacja na pole 1, ruch o 2 na pole 3, ruch o 3 na pole 1