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$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $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$。

输出格式

对于每个测试用例，输出一行，包含 $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