A. Circular Board Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Wandering past the fresh produce, Busy Beaver's attention is captured by the local dairy vendor with a peculiar board game at his stall.

There is a circular board with $$$N$$$ squares numbered from $$$0$$$ to $$$N-1$$$. Busy Beaver plays a game on this board with an $$$N$$$ sided die labelled from $$$0$$$ to $$$N-1$$$. If he is on square $$$s$$$ and moves by $$$t$$$ steps, he will land directly on the square $$$s+t \pmod N$$$.

There is also one magical portal on the board, such that if the player lands exactly on square $$$X$$$, they are instantly teleported to square $$$Y$$$.

Busy Beaver rolls the die $$$K$$$ times and obtains the sequence $$$a_1, a_2, \dots, a_K$$$. From his initial square, Busy Beaver will move by $$$a_1$$$ steps, then by $$$a_2$$$ steps, and so on until he has completed all $$$K$$$ moves, where he moves by $$$a_i$$$ on the $$$i$$$-th move.

For each possible initial square from $$$0$$$ to $$$N-1$$$ (inclusive, except square $$$X$$$), determine the square that Busy Beaver lands on after all $$$K$$$ moves are completed (including any teleports).

Input

The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 2 \cdot 10^3$$$).

The first line of each test case contains four integers $$$N$$$, $$$K$$$, $$$X$$$, and $$$Y$$$ ($$$2 \le N \le 5 \cdot 10^5$$$, $$$1 \le K \le 5 \cdot 10^5$$$, $$$0 \le X, Y \lt N$$$, $$$X \ne Y$$$).

The second line of each test case contains $$$K$$$ integers $$$a_1, a_2, \dots, a_K$$$ ($$$0 \le a_i \lt N$$$).

The sum of $$$N$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

The sum of $$$K$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output $$$N-1$$$ integers representing the square that Busy Beaver would land on if he started on square $$$i$$$, for all $$$0 \le i \lt N$$$ except for $$$i = X$$$.

Scoring

There are two subtasks for this problem.

  • ($$$20$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$5 \cdot 10^3$$$, and the sum of $$$K$$$ across all test cases does not exceed $$$5 \cdot 10^3$$$.
  • ($$$80$$$ points): No additional constraints.
Example
Input
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
Output
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
Note

In the first sample test case, there are $$$5$$$ squares on the board and one die roll that rolls $$$1$$$. The portal teleports the player from square $$$0$$$ to square $$$1$$$. For each of the starting squares, here is the sequence of events:

  • $$$0$$$: The portal teleports from this square; we do not need to output anything.
  • $$$1$$$: starts on square $$$1$$$, moves by $$$1$$$ to square $$$2$$$
  • $$$2$$$: starts on square $$$2$$$, moves by $$$1$$$ to square $$$3$$$
  • $$$3$$$: starts on square $$$3$$$, moves by $$$1$$$ to square $$$4$$$
  • $$$4$$$: starts on square $$$4$$$, moves by $$$1$$$ to square $$$0$$$ and teleports to square $$$1$$$

In the second sample test case, there are $$$5$$$ squares on the board and three die rolls that roll $$$1,2,3$$$ respectively. The portal teleports the player from square $$$0$$$ to square $$$1$$$. For each of the starting squares, here is the sequence of events:

  • $$$0$$$: The portal teleports from this square; we do not need to output anything.
  • $$$1$$$: starts on square $$$1$$$, moves by $$$1$$$ to square $$$2$$$, moves by $$$2$$$ to square $$$4$$$, moves by $$$3$$$ to square $$$2$$$
  • $$$2$$$: starts on square $$$2$$$, moves by $$$1$$$ to square $$$3$$$, moves by $$$2$$$ to square $$$0$$$ and teleports to square $$$1$$$, moves by $$$3$$$ to square $$$4$$$
  • $$$3$$$: starts on square $$$3$$$, moves by $$$1$$$ to square $$$4$$$, moves by $$$2$$$ to square $$$1$$$, moves by $$$3$$$ to square $$$4$$$
  • $$$4$$$: starts on square $$$4$$$, moves by $$$1$$$ to square $$$0$$$ and teleports to square $$$1$$$, moves by $$$2$$$ to square $$$3$$$, moves by $$$3$$$ to square $$$1$$$