Дориян подарил господину Нежмаху очень замысловатый музыкальный инструмент. Инструмент может проигрывать $m$ различных нот, пронумерованных от $0$ до $m - 1$. Интересно, что он может сыграть мелодию из $n$ нот $s_0, \dots, s_{n-1}$ только тогда, когда $n$ — простое число и выполняются следующие условия:

• последовательность возрастает, то есть $s_i < s_{i+1}$ для всех $0 \le i < n - 1$,
• существуют такие $a, b, c$ и $d$, что $s_{(a + b \cdot i) \bmod n} = (c + d \cdot i) \bmod m$ для всех $0 \le i < n$, где $0 \le a < n$, $1 \le b < n$ и $0 \le c < m$, $1 \le d < m$.

Заметим, что такие $a, b, c$ и $d$ однозначно задают последовательность. Сейчас Нежмах сочиняет новую мелодию и уже заполнил некоторые позиции нотами. Помогите ему закончить мелодию! Достаточно вывести любые $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$, где $u_i = -1$, если Нежмах ещё не решил, какая нота должна звучать на этой позиции).

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $3 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите $1$ строку с $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