$0$부터 $N-1$까지 번호가 매겨진 $N$개의 칸이 있는 원형 보드가 있습니다. Busy Beaver는 이 보드에서 $0$부터 $N-1$까지의 눈을 가진 $N$면체 주사위를 사용하여 게임을 합니다. 만약 현재 $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$번의 이동을 모두 마칠 때까지 이동합니다.
$0$부터 $N-1$까지의 모든 가능한 초기 칸(단, $X$번 칸은 제외)에 대하여, $K$번의 이동(모든 순간 이동 포함)을 모두 마친 후 Busy Beaver가 도착하게 될 칸을 구하세요.
입력
첫 번째 줄에는 테스트 케이스의 수 $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$을 넘지 않습니다.
출력
각 테스트 케이스마다, $i=X$를 제외한 모든 $0 \le i < N$에 대하여, $i$번 칸에서 시작했을 때 Busy Beaver가 최종적으로 도착하는 칸을 나타내는 $N-1$개의 정수를 출력하세요.
서브태스크
- (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$번 칸에 도착