分数: 800 点
问题陈述
给你整数 N,M,K 和一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。保证每个元素 A 介于 0 和 M-1,包括在内。
您可以对整数序列执行以下操作 A 之间 0 和 K 次,包括:
- 选择一对整数 (l,r) 满意 1\le l\le r\le N,并替换 A_k 与 (A_k+1) \bmod M 对于每个 k=l,l+1,\ldots,r.
查找字典顺序最小的 A 操作后。
你被给予 T 测试用例;解决它们中的每一个。
序列的字典顺序是什么?
一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果满足以下条件之一。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两项成立。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i (在数值上)小于 T_i.
约束
- 1\le T\le 3\times 10^5
- 1\le N\le 3\times 10^5
- 2\le M\le 10^9
- 1\le K\le 10^{15}
- 0\le A_i < M
- 总和 一个输入文件中的 N 所有测试用例最多 3\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M K A_1 A_2 \ldots A_N
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出字典顺序最小的元素 A 运算后,用空格分隔。
示例输入 1
3 4 6 3 2 5 4 1 4 17 100 2 0 2 6 5 10 6 2 6 5 3 9
示例输出 1
2 0 0 1 0 0 0 0 2 0 0 3 0
考虑第一个测试用例。
通过执行如下两个操作,我们可以得到 A=(2,0,0,1).
- 操作 1:选择 (l,r)=(2,3)。现在 A=(2,0,5,1).
- 操作 2:选择 (l,r)=(3,3)。现在 A=(2,0,0,1).