Dorijan은 Nežmah 씨에게 매우 정교한 악기를 선물했다. 이 악기는 $0$부터 $m - 1$까지 번호가 매겨진 $m$개의 서로 다른 음표를 연주할 수 있다. 흥미롭게도, 이 악기는 $n$이 소수이고 다음 조건이 성립할 때만 $n$개의 음표로 이루어진 곡 $s_0, \dots, s_{n-1}$을 연주할 수 있다.

• 수열이 증가한다. 즉, 모든 $0 \le i < n - 1$에 대해 $s_i < s_{i+1}$이다.
• 모든 $0 \le i < n$에 대해 $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$을 만족하는 $a, b, c$와 $d$가 존재한다(단, $0 \le a < n$, $1 \le b < n$, $0 \le c < m$, $1 \le d < m$).

이러한 $a, b, c$와 $d$는 주어진 수열을 유일하게 결정한다는 점에 유의하라. Nežmah는 현재 새로운 곡을 작곡하고 있으며, 이미 일부 위치에 음표를 채워 넣었다. 그가 곡을 완성할 수 있도록 도와주자! Nežmah가 이미 정해 놓은 위치의 음표들과 일치하는 유효한 수열을 정의하는 $a, b, c$와 $d$를 아무것이나 출력하면 충분하다. 해가 존재함이 보장된다.

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 하나의 정수 $t$ ($1 \le t \le 2 \cdot 10^4$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 $2$개의 정수 $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$을 초과하지 않음이 보장된다.

출력

각 테스트 케이스마다 요구되는 $a$, $b$, $c$, $d$의 값을 나타내는 $4$개의 정수를 $1$줄에 출력한다. 가능한 답이 여러 개라면 그중 아무것이나 출력한다.

예제

입력 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