En flânant devant les produits frais, l'attention de Busy Beaver est captivée par le marchand de produits laitiers local avec un jeu de plateau particulier sur son étal.
Il existe un plateau circulaire avec $N$ cases numérotées de $0$ à $N - 1$. Busy Beaver joue à un jeu sur ce plateau avec un dé à $N$ faces numérotées de $0$ à $N - 1$. S'il est sur la case $s$ et se déplace de $t$ pas, il atterrira directement sur la case $s + t \pmod N$.
Il y a également un portail magique sur le plateau, tel que si le joueur atterrit exactement sur la case $X$, il est instantanément téléporté sur la case $Y$.
Busy Beaver lance le dé $K$ fois et obtient la séquence $a_1, a_2, \dots, a_K$. Depuis sa case initiale, Busy Beaver se déplacera de $a_1$ pas, puis de $a_2$ pas, et ainsi de suite jusqu'à ce qu'il ait terminé tous les $K$ mouvements, où il se déplace de $a_i$ lors du $i$-ème mouvement.
Pour chaque case initiale possible de $0$ à $N - 1$ (inclus, sauf la case $X$), déterminez la case sur laquelle Busy Beaver atterrit après que tous les $K$ mouvements sont terminés (en incluant toute téléportation).
Entrée
La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 2 \cdot 10^3$).
La première ligne de chaque cas de test contient quatre entiers $N, K, X$ et $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 deuxième ligne de chaque cas de test contient $K$ entiers $a_1, a_2, \dots, a_K$ ($0 \le a_i < N$).
La somme de $N$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.
La somme de $K$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez $N - 1$ entiers représentant la case sur laquelle Busy Beaver atterrirait s'il commençait sur la case $i$, pour tout $0 \le i < N$ sauf pour $i = X$.
Barème
- (20 points) : La somme de $N$ sur tous les cas de test ne dépasse pas $5 \cdot 10^3$, et la somme de $K$ sur tous les cas de test ne dépasse pas $5 \cdot 10^3$.
- (80 points) : Aucune contrainte supplémentaire.
Exemples
| Entrée | Sortie |
|---|---|
| 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 |
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 |
Remarque
Dans le premier cas de test, il y a 5 cases sur le plateau et un lancer de dé qui donne 1. Le portail téléporte le joueur de la case 0 à la case 1. Pour chacune des cases de départ, voici la séquence des événements :
- 0 : Le portail téléporte depuis cette case ; nous n'avons rien à afficher.
- 1 : commence sur la case 1, se déplace de 1 vers la case 2
- 2 : commence sur la case 2, se déplace de 1 vers la case 3
- 3 : commence sur la case 3, se déplace de 1 vers la case 4
- 4 : commence sur la case 4, se déplace de 1 vers la case 0 et est téléporté vers la case 1
Dans le deuxième cas de test, il y a 5 cases sur le plateau et trois lancers de dé qui donnent 1, 2, 3 respectivement. Le portail téléporte le joueur de la case 0 à la case 1. Pour chacune des cases de départ, voici la séquence des événements :
- 0 : Le portail téléporte depuis cette case ; nous n'avons rien à afficher.
- 1 : commence sur la case 1, se déplace de 1 vers la case 2, se déplace de 2 vers la case 4, se déplace de 3 vers la case 2
- 2 : commence sur la case 2, se déplace de 1 vers la case 3, se déplace de 2 vers la case 0 et est téléporté vers la case 1, se déplace de 3 vers la case 4
- 3 : commence sur la case 3, se déplace de 1 vers la case 4, se déplace de 2 vers la case 1, se déplace de 3 vers la case 4
- 4 : commence sur la case 4, se déplace de 1 vers la case 0 et est téléporté vers la case 1, se déplace de 2 vers la case 3, se déplace de 3 vers la case 1