Mientras paseaba frente a los productos frescos, la atención de Busy Beaver fue capturada por el vendedor de lácteos local con un peculiar juego de mesa en su puesto.

Hay un tablero circular con $N$ casillas numeradas del $0$ al $N - 1$. Busy Beaver juega un juego en este tablero con un dado de $N$ caras numeradas del $0$ al $N - 1$. Si está en la casilla $s$ y se mueve $t$ pasos, aterrizará directamente en la casilla $s + t \pmod N$.

También hay un portal mágico en el tablero, de tal manera que si el jugador aterriza exactamente en la casilla $X$, es teletransportado instantáneamente a la casilla $Y$.

Busy Beaver lanza el dado $K$ veces y obtiene la secuencia $a_1, a_2, \dots, a_K$. Desde su casilla inicial, Busy Beaver se moverá $a_1$ pasos, luego $a_2$ pasos, y así sucesivamente hasta completar los $K$ movimientos, donde se mueve $a_i$ pasos en el $i$-ésimo movimiento.

Para cada posible casilla inicial desde $0$ hasta $N - 1$ (inclusive, excepto la casilla $X$), determine la casilla en la que aterriza Busy Beaver después de completar todos los $K$ movimientos (incluyendo cualquier teletransporte).

Entrada

La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 2 \cdot 10^3$).

La primera línea de cada caso de prueba contiene cuatro enteros $N, K, X$ y $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$).

La segunda línea de cada caso de prueba contiene $K$ enteros $a_1, a_2, \dots, a_K$ ($0 \le a_i < N$).

La suma de $N$ en todos los casos de prueba no supera $5 \cdot 10^5$.

La suma de $K$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprima $N - 1$ enteros que representen la casilla en la que aterrizaría Busy Beaver si comenzara en la casilla $i$, para todo $0 \le i < N$ excepto para $i = X$.

Subtareas

Hay dos subtareas para este problema.

• (20 puntos): La suma de $N$ en todos los casos de prueba no supera $5 \cdot 10^3$, y la suma de $K$ en todos los casos de prueba no supera $5 \cdot 10^3$.
• (80 puntos): Sin restricciones adicionales.

Ejemplos

Entrada 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

Salida 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

Nota

En el primer caso de prueba de ejemplo, hay 5 casillas en el tablero y un lanzamiento de dado que resulta en 1. El portal teletransporta al jugador de la casilla 0 a la casilla 1. Para cada una de las casillas de inicio, aquí está la secuencia de eventos:

• 0: El portal teletransporta desde esta casilla; no necesitamos imprimir nada.
• 1: comienza en la casilla 1, se mueve 1 paso a la casilla 2
• 2: comienza en la casilla 2, se mueve 1 paso a la casilla 3
• 3: comienza en la casilla 3, se mueve 1 paso a la casilla 4
• 4: comienza en la casilla 4, se mueve 1 paso a la casilla 0 y se teletransporta a la casilla 1

En el segundo caso de prueba de ejemplo, hay 5 casillas en el tablero y tres lanzamientos de dado que resultan en 1, 2, 3 respectivamente. El portal teletransporta al jugador de la casilla 0 a la casilla 1. Para cada una de las casillas de inicio, aquí está la secuencia de eventos:

• 0: El portal teletransporta desde esta casilla; no necesitamos imprimir nada.
• 1: comienza en la casilla 1, se mueve 1 paso a la casilla 2, se mueve 2 pasos a la casilla 4, se mueve 3 pasos a la casilla 2
• 2: comienza en la casilla 2, se mueve 1 paso a la casilla 3, se mueve 2 pasos a la casilla 0 y se teletransporta a la casilla 1, se mueve 3 pasos a la casilla 4
• 3: comienza en la casilla 3, se mueve 1 paso a la casilla 4, se mueve 2 pasos a la casilla 1, se mueve 3 pasos a la casilla 4
• 4: comienza en la casilla 4, se mueve 1 paso a la casilla 0 y se teletransporta a la casilla 1, se mueve 2 pasos a la casilla 3, se mueve 3 pasos a la casilla 1