Dorijan menghadiahkan sebuah instrumen yang sangat rumit kepada Tuan Nežmah. Instrumen tersebut dapat memainkan $m$ nada berbeda yang dinomori dari $0$ hingga $m - 1$. Menariknya, instrumen tersebut hanya dapat memainkan sebuah lagu yang terdiri dari $n$ nada $s_0, \dots, s_{n-1}$ ketika $n$ adalah bilangan prima dan hal berikut terpenuhi:

• barisannya menaik, yaitu $s_i < s_{i+1}$ untuk semua $0 \le i < n - 1$,
• terdapat $a, b, c$ dan $d$ sehingga $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ untuk semua $0 \le i < n$, dengan $0 \le a < n$, $1 \le b < n$ serta $0 \le c < m$, $1 \le d < m$.

Perhatikan bahwa $a, b, c$ dan $d$ tersebut secara unik mendefinisikan barisan yang diberikan. Saat ini Nežmah sedang menggubah sebuah lagu baru, dan ia telah mengisi beberapa posisi dengan nada. Bantulah ia menyelesaikan lagu tersebut! Cukup keluarkan nilai $a, b, c$ dan $d$ mana saja yang mendefinisikan barisan valid yang cocok pada posisi-posisi yang telah ditetapkan oleh Nežmah. Dijamin bahwa solusi selalu ada.

Masukan

Baris pertama berisi satu bilangan bulat $t$ ($1 \le t \le 2 \cdot 10^4$), banyaknya kasus uji.

Baris pertama dari setiap kasus uji berisi $2$ bilangan bulat $n$ dan $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ adalah bilangan prima, $n \le m \le 10^9$).

Baris kedua dari setiap kasus uji berisi larik hasil ($-1 \le u_i < m$, dengan $u_i = -1$ jika Nežmah belum memutuskan nada mana yang harus dimainkan pada posisi ini).

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $3 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan $1$ baris berisi $4$ bilangan bulat: nilai-nilai $a$, $b$, $c$, dan $d$ yang diminta. Jika terdapat beberapa kemungkinan jawaban, keluarkan yang mana saja.

Contoh

Masukan 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

Keluaran 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