Dorijan は Nežmah 氏に非常に精巧な楽器を贈りました。この楽器は $0$ から $m - 1$ までの番号が付けられた $m$ 種類の異なる音符を演奏できます。興味深いことに、この楽器が $n$ 個の音符からなる曲 $s_0, \dots, s_{n-1}$ を演奏できるのは、$n$ が素数であり、かつ以下の条件が成り立つときに限られます。

• 数列が狭義単調増加である、すなわちすべての $0 \le i < n - 1$ に対して $s_i < s_{i+1}$ が成り立つ。
• ある $a, b, c$ と $d$ が存在して、すべての $0 \le i < n$ に対して $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ が成り立つ（ただし $0 \le a < n$, $1 \le b < n$, $0 \le c < m$, $1 \le d < m$）。

このような $a, b, c$ と $d$ は与えられた数列を一意に定めることに注意してください。Nežmah は現在新しい曲を作曲しており、いくつかの位置にはすでに音符を入れています。彼が曲を完成させるのを手伝ってください！Nežmah がすでに設定した位置で一致するような有効な数列を定める $a, b, c$ と $d$ を 1 組出力すれば十分です。解が存在することは保証されています。

入力

1 行目には、テストケースの個数を表す単一の整数 $t$（$1 \le t \le 2 \cdot 10^4$）が与えられます。

各テストケースの 1 行目には、$2$ つの整数 $n$ と $m$（$3 \le n \le 3 \cdot 10^5$、$n$ は素数、$n \le m \le 10^9$）が与えられます。

各テストケースの 2 行目には、結果の配列（$-1 \le u_i < m$、ただし Nežmah がその位置でどの音符を演奏するかまだ決めていない場合は $u_i = -1$）が与えられます。

すべてのテストケースにおける $n$ の総和は $3 \cdot 10^5$ を超えないことが保証されます。

出力

各テストケースについて、求める $a$, $b$, $c$, $d$ の値を表す $4$ つの整数を $1$ 行に出力してください。可能な答えが複数存在する場合は、どれを出力しても構いません。

入出力例

入力 1

8
7 12
0 2 4 5 7 9 11
5 19
-1 4 -1 12 -1
3 7
1 4 -1
7 35
2 -1 12 -1 -1 27 -1
5 14
0 -1 11 -1 -1
3 6
-1 -1 2
3 16
-1 -1 -1
5 14
-1 1 -1 9 -1

出力 1

3 4 5 7
2 2 7 8
2 1 5 3
0 1 2 5
1 4 1 13
0 1 0 1
0 1 0 1
1 3 1 9