Có một bàn cờ hình tròn với $N$ ô được đánh số từ $0$ đến $N - 1$. Busy Beaver chơi một trò chơi trên bàn cờ này với một con xúc xắc $N$ mặt được đánh số từ $0$ đến $N - 1$. Nếu người chơi đang ở ô $s$ và di chuyển $t$ bước, người chơi sẽ dừng lại trực tiếp tại ô $s + t \pmod N$.

Trên bàn cờ còn có một cổng dịch chuyển kỳ diệu, sao cho nếu người chơi dừng lại chính xác tại ô $X$, họ sẽ ngay lập tức được dịch chuyển đến ô $Y$.

Busy Beaver tung xúc xắc $K$ lần và thu được dãy số $a_1, a_2, \dots, a_K$. Từ ô xuất phát, Busy Beaver sẽ di chuyển $a_1$ bước, sau đó $a_2$ bước, và cứ tiếp tục như vậy cho đến khi hoàn thành tất cả $K$ lượt di chuyển, trong đó người chơi di chuyển $a_i$ bước ở lượt thứ $i$.

Với mỗi ô xuất phát có thể từ $0$ đến $N - 1$ (bao gồm cả các ô, ngoại trừ ô $X$), hãy xác định ô mà Busy Beaver dừng lại sau khi hoàn thành tất cả $K$ lượt di chuyển (bao gồm cả các lần dịch chuyển).

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test $T$ ($1 \le T \le 2 \cdot 10^3$).

Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên $N, K, X$ và $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$).

Dòng thứ hai của mỗi bộ test chứa $K$ số nguyên $a_1, a_2, \dots, a_K$ ($0 \le a_i < N$).

Tổng $N$ trên tất cả các bộ test không vượt quá $5 \cdot 10^5$.

Tổng $K$ trên tất cả các bộ test không vượt quá $5 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ test, in ra $N - 1$ số nguyên đại diện cho ô mà Busy Beaver sẽ dừng lại nếu bắt đầu từ ô $i$, với mọi $0 \le i < N$ ngoại trừ $i = X$.

Nhiệm vụ con

Có hai nhiệm vụ con cho bài toán này:

• (20 điểm): Tổng $N$ trên tất cả các bộ test không vượt quá $5 \cdot 10^3$, và tổng $K$ trên tất cả các bộ test không vượt quá $5 \cdot 10^3$.
• (80 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 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

Ví dụ 2

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

Ghi chú

Trong bộ test mẫu đầu tiên, có 5 ô trên bàn cờ và một lần tung xúc xắc ra 1. Cổng dịch chuyển người chơi từ ô 0 đến ô 1. Với mỗi ô xuất phát, đây là chuỗi sự kiện:

• 0: Cổng dịch chuyển từ ô này; chúng ta không cần in ra bất cứ điều gì.
• 1: bắt đầu tại ô 1, di chuyển 1 bước đến ô 2
• 2: bắt đầu tại ô 2, di chuyển 1 bước đến ô 3
• 3: bắt đầu tại ô 3, di chuyển 1 bước đến ô 4
• 4: bắt đầu tại ô 4, di chuyển 1 bước đến ô 0 và dịch chuyển đến ô 1

Trong bộ test mẫu thứ hai, có 5 ô trên bàn cờ và ba lần tung xúc xắc ra 1, 2, 3 tương ứng. Cổng dịch chuyển người chơi từ ô 0 đến ô 1. Với mỗi ô xuất phát, đây là chuỗi sự kiện:

• 0: Cổng dịch chuyển từ ô này; chúng ta không cần in ra bất cứ điều gì.
• 1: bắt đầu tại ô 1, di chuyển 1 bước đến ô 2, di chuyển 2 bước đến ô 4, di chuyển 3 bước đến ô 2
• 2: bắt đầu tại ô 2, di chuyển 1 bước đến ô 3, di chuyển 2 bước đến ô 0 và dịch chuyển đến ô 1, di chuyển 3 bước đến ô 4
• 3: bắt đầu tại ô 3, di chuyển 1 bước đến ô 4, di chuyển 2 bước đến ô 1, di chuyển 3 bước đến ô 4
• 4: bắt đầu tại ô 4, di chuyển 1 bước đến ô 0 và dịch chuyển đến ô 1, di chuyển 2 bước đến ô 3, di chuyển 3 bước đến ô 1