I. Intricate Instrument
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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, \ldots, s_{n-1}$$$ only when $$$n$$$ is $$$\textbf{prime}$$$ and the following is true

  • the sequence is increasing i.e. $$$s_i \lt s_{i + 1}$$$ for all $$$0 \leq i \lt n-1$$$
  • there exist $$$a, b, c$$$ and $$$d$$$ such that $$$s_{(a+b\cdot i)\mod n} = (c + d\cdot i) \mod m$$$ for all $$$0 \leq i \lt n$$$, where $$$0 \leq a \lt n,\; 1 \leq b \lt n$$$ and $$$0 \leq c \lt m,\; 1 \leq d \lt 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 \leq t \leq 2 \cdot 10^4$$$), the number of test cases.

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

The second line of each test case contains the resulting array ($$$-1 \leq u_i \lt 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
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
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