Dorijan gifted Mr. Nežmah a very intricate instrument. The instrument can play $m$ different notes numbered from $0$ to $m - 1$. Interestingly, it can play a tune of $n$ notes $s_0, \dots, s_{n-1}$ only when $n$ is prime and the following is true:

• the sequence is increasing, i.e. $s_i < s_{i+1}$ for all $0 \le i < n - 1$,
• there exist $a, b, c$ and $d$ such that $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ for all $0 \le i < n$, where $0 \le a < n$, $1 \le b < n$ and $0 \le c < m$, $1 \le d < m$.

Notice that such $a, b, c$ and $d$ uniquely define the given sequence. Nežmah is currently composing a new tune, and he has already filled up some positions with notes. Help him finish the tune! It is enough to output any $a, b, c$ and $d$ which define a valid sequence that matches in the positions Nežmah has already set. It is guaranteed that a solution exists.

Input

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$), the number of test cases.

The first line of each test case contains $2$ integers $n$ and $m$ ($3 \le n \le 3 \cdot 10^5$, $n$ is prime, $n \le m \le 10^9$).

The second line of each test case contains the resulting array ($-1 \le u_i < m$, where $u_i = -1$ if Nežmah hasn't yet decided which note should be played in this position).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output $1$ line with $4$ integers: the required values of $a$, $b$, $c$, and $d$. If there are multiple possible answers, output any of them.

Example

Input 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

Output 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