#P17957. Intricate Instrument
Intricate Instrument
Intricate Instrument
题目描述
一个乐器可以演奏 种音符,编号为 。
长度为 的音符序列 可以被这个乐器演奏,当且仅当 为素数,并满足下列条件:
- 序列严格递增,即对所有 ,都有 。
- 存在四个整数 ,满足 、、、,并且对每个 都有
这里的取模结果为最小非负余数。由于 为素数且 ,四个参数会唯一确定整个序列。
现在序列中的部分位置已经确定,其他位置尚未确定。请找出任意一组参数 ,使生成的序列严格递增,并且与所有已知位置一致。保证存在解。
输入格式
第一行一个整数 ,表示测试用例数,。
每组测试用例的第一行包含两个整数 ,满足 , 是素数,。
第二行包含 个整数 ,满足 。当 时,该位置未知;否则要求 。
所有测试用例的 之和不超过 。每组输入均保证存在满足所有条件的参数。
输出格式
每组测试用例输出一行四个整数 ,满足题目中的范围与条件。
若存在多个答案,输出任意一个即可。序列位置与参数 均按从 开始的下标解释。
样例 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