Dorijan 送咗一件好精密嘅樂器畀 Nežmah 先生。呢件樂器可以彈奏 $m$ 個唔同嘅音符，由 $0$ 到 $m - 1$ 編號。好得意嘅係，只有當 $n$ 係質數而且滿足以下條件嗰陣，佢先至可以彈奏出由 $n$ 個音符組成嘅旋律 $s_0, \dots, s_{n-1}$：

• 序列係遞增嘅，即係對於所有 $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 而家正喺度作緊一首新曲，而且佢已經喺某啲位置度填好咗音符。請幫佢完成呢首曲啦！只需要輸出任何一組 $a, b, c$ 同 $d$，令佢哋定義出嚟嘅合法序列喺 Nežmah 已經填好嘅位置上面完全吻合就得。保證一定有解。

輸入格式

第一行包含一個整數 $t$（$1 \le t \le 2 \cdot 10^4$），表示測試資料嘅組數。

每組測試資料嘅第一行包含 $2$ 個整數 $n$ 同 $m$（$3 \le n \le 3 \cdot 10^5$，$n$ 係質數，$n \le m \le 10^9$）。

每組測試資料嘅第二行包含結果陣列（$-1 \le u_i < m$，其中如果 Nežmah 仲未決定呢個位置應該彈邊個音符，則 $u_i = -1$）。

保證所有測試資料入面 $n$ 嘅總和唔超過 $3 \cdot 10^5$。

輸出格式

對於每組測試資料，輸出 $1$ 行包含 $4$ 個整數：所需嘅 $a$、$b$、$c$ 同 $d$ 嘅值。如果有多個可能嘅答案，輸出其中任何一個即可。

範例

輸入 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