#P17957. Intricate Instrument

Intricate Instrument

Intricate Instrument

题目描述

一个乐器可以演奏 mm 种音符,编号为 0,1,…,m−10,1,\ldots,m-1。

长度为 nn 的音符序列 s0,s1,…,sn−1s_0,s_1,\ldots,s_{n-1} 可以被这个乐器演奏,当且仅当 nn 为素数,并满足下列条件:

  • 序列严格递增,即对所有 0≤i<n−10\le i<n-1,都有 si<si+1s_i<s_{i+1}。
  • 存在四个整数 a,b,c,da,b,c,d,满足 0≤a<n0\le a<n、1≤b<n1\le b<n、0≤c<m0\le c<m、1≤d<m1\le d<m,并且对每个 0≤i<n0\le i<n 都有
s(a+bi) mod n=(c+di) mod m.s_{(a+b i)\bmod n}=(c+d i)\bmod m.

这里的取模结果为最小非负余数。由于 nn 为素数且 1≤b<n1\le b<n,四个参数会唯一确定整个序列。

现在序列中的部分位置已经确定,其他位置尚未确定。请找出任意一组参数 a,b,c,da,b,c,d,使生成的序列严格递增,并且与所有已知位置一致。保证存在解。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤2⋅1041\le t\le2\cdot10^4。

每组测试用例的第一行包含两个整数 n,mn,m,满足 3≤n≤3⋅1053\le n\le3\cdot10^5,nn 是素数,n≤m≤109n\le m\le10^9。

第二行包含 nn 个整数 u0,u1,…,un−1u_0,u_1,\ldots,u_{n-1},满足 −1≤ui<m-1\le u_i<m。当 ui=−1u_i=-1 时,该位置未知;否则要求 si=uis_i=u_i。

所有测试用例的 nn 之和不超过 3⋅1053\cdot10^5。每组输入均保证存在满足所有条件的参数。

输出格式

每组测试用例输出一行四个整数 a,b,c,da,b,c,d,满足题目中的范围与条件。

若存在多个答案,输出任意一个即可。序列位置与参数 aa 均按从 00 开始的下标解释。

样例 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

输出

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