Дориян Нежмах мырзаға өте күрделі музыкалық аспап сыйлады. Бұл аспап $0$-ден $m - 1$-ге дейін нөмірленген $m$ түрлі нотаны ойнай алады. Қызығы, ол $n$ нотадан тұратын $s_0, \dots, s_{n-1}$ әуенін тек $n$ жай сан болғанда және келесі шарттар орындалғанда ғана ойнай алады:

• тізбек өспелі, яғни барлық $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$ берілген тізбекті бірмәнді анықтайтынына назар аударыңыз. Қазіргі уақытта Нежмах жаңа әуен шығарып жатыр және ол кейбір орындарды ноталармен толтырып қойған. Оған әуенді аяқтауға көмектесіңіз! Нежмах бекітіп қойған орындарда сәйкес келетін жарамды тізбекті анықтайтын кез келген $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$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін $4$ бүтін саннан тұратын $1$ жол шығарыңыз: $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