Dorijan đã tặng ông Nežmah một nhạc cụ rất tinh xảo. Nhạc cụ này có thể chơi $m$ nốt nhạc khác nhau được đánh số từ $0$ đến $m - 1$. Thú vị thay, nó chỉ có thể chơi một giai điệu gồm $n$ nốt nhạc $s_0, \dots, s_{n-1}$ khi $n$ là số nguyên tố và các điều kiện sau đây được thỏa mãn:

• dãy số tăng nghiêm ngặt, tức là $s_i < s_{i+1}$ với mọi $0 \le i < n - 1$,
• tồn tại $a, b, c$ và $d$ sao cho $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ với mọi $0 \le i < n$, trong đó $0 \le a < n$, $1 \le b < n$ và $0 \le c < m$, $1 \le d < m$.

Lưu ý rằng các số $a, b, c$ và $d$ như vậy xác định duy nhất dãy số đã cho. Nežmah hiện đang sáng tác một giai điệu mới, và ông đã điền sẵn nốt nhạc vào một số vị trí. Hãy giúp ông ấy hoàn thành giai điệu! Chỉ cần in ra bất kỳ bộ $a, b, c$ và $d$ nào xác định một dãy hợp lệ khớp với các vị trí mà Nežmah đã đặt sẵn. Đảm bảo rằng luôn tồn tại lời giải.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 2 \cdot 10^4$), là số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa $2$ số nguyên $n$ và $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ là số nguyên tố, $n \le m \le 10^9$).

Dòng thứ hai của mỗi bộ dữ liệu chứa mảng kết quả ($-1 \le u_i < m$, trong đó $u_i = -1$ nếu Nežmah vẫn chưa quyết định nốt nhạc nào sẽ được chơi ở vị trí này).

Đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $3 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra $1$ dòng gồm $4$ số nguyên: các giá trị cần tìm của $a$, $b$, $c$ và $d$. Nếu có nhiều đáp án khả dĩ, hãy in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 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

Kết quả 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