有一个圆形的棋盘，上面有 $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$ 的每个可能的初始方格（包含 $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$ 个整数，表示如果从方格 $i$ 开始，Busy Beaver 最终落下的方格，输出需涵盖所有 $0 \le i < N$ 且 $i \neq 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

说明

在第一个样例测试用例中，棋盘上有 $5$ 个方格，掷了一次骰子，结果为 $1$。传送门将玩家从方格 $0$ 传送到方格 $1$。对于每个起始方格，事件序列如下：

• $0$：传送门从该方格传送；我们不需要输出任何内容。
• $1$：从方格 $1$ 开始，移动 $1$ 步到方格 $2$。
• $2$：从方格 $2$ 开始，移动 $1$ 步到方格 $3$。
• $3$：从方格 $3$ 开始，移动 $1$ 步到方格 $4$。
• $4$：从方格 $4$ 开始，移动 $1$ 步到方格 $0$ 并传送到方格 $1$。

在第二个样例测试用例中，棋盘上有 $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$。