Busy Beaver は、新鮮な農産物の間を歩き回っているうちに、屋台で売られている奇妙なボードゲームに目を奪われました。

このボードゲームには、$0$ から $N-1$ まで番号が振られた $N$ 個のマスがある円形のボードがあります。Busy Beaver は、$0$ から $N-1$ までの目がついた $N$ 面ダイスを使ってこのボードで遊びます。彼がマス $s$ にいて $t$ ステップ移動する場合、彼は直接マス $s+t \pmod N$ に着きます。

ボード上には魔法のポータルが1つあり、プレイヤーがちょうどマス $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$ までの各可能な初期マス（マス $X$ を除く）について、$K$ 回の移動（テレポートを含む）がすべて完了した後に Busy Beaver が着くマスを求めてください。

入力

入力の最初の行にはテストケースの数 $T$ ($1 \le T \le 2 \cdot 10^3$) が含まれます。

各テストケースの最初の行には、4つの整数 $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$) が含まれます。

各テストケースの2行目には、$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$ 個の整数を出力してください。

小課題

この問題には2つの小課題があります。

• (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回振られ、その目は1です。ポータルはプレイヤーをマス $0$ からマス $1$ へテレポートさせます。各開始マスにおけるイベントの順序は以下の通りです。

• $0$: このマスからはポータルでテレポートするため、何も出力する必要はありません。
• $1$: マス $1$ から開始し、$1$ 移動してマス $2$ へ。
• $2$: マス $2$ から開始し、$1$ 移動してマス $3$ へ。
• $3$: マス $3$ から開始し、$1$ 移動してマス $4$ へ。
• $4$: マス $4$ から開始し、$1$ 移動してマス $0$ へ、そしてマス $1$ にテレポート。

2番目のサンプルテストケースでは、ボード上に5つのマスがあり、ダイスは3回振られ、その目は順に $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$ へ。