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