/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
整数 N,M,K と長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。A の各要素は 0 以上 M 未満であることが保証されます。
あなたは整数列 A に対して以下の操作を 0 回以上 K 回以下行うことができます：
- 1\le l\le r\le N を満たす整数の組 (l,r) を選び、k=l,l+1,\ldots,r に対し A_k を (A_k+1) \bmod M で置き換える。
辞書順最小となる操作後の A を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|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 が存在して、下記の 2 つがともに成り立つ。
- (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
1 番目のテストケースについて考えます。
以下のように 2 回操作することで 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) となる。
Score : 800 points
Problem Statement
You are given integers N,M,K and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that each element of A is between 0 and M-1, inclusive.
You may perform the following operation on the integer sequence A between 0 and K times, inclusive:
- Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and replace A_k with (A_k+1) \bmod M for each k=l,l+1,\ldots,r.
Find the lexicographically smallest A after the operations.
You are given T test cases; solve each of them.
What is lexicographic order on sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if one of the following conditions holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i is (numerically) smaller than T_i.
Constraints
- 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
- The sum of N over all test cases is at most 3\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M K A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, output the elements of the lexicographically smallest A after the operations, separated by spaces.
Sample Input 1
3 4 6 3 2 5 4 1 4 17 100 2 0 2 6 5 10 6 2 6 5 3 9
Sample Output 1
2 0 0 1 0 0 0 0 2 0 0 3 0
Consider the first test case.
By performing two operations as follows, we can obtain A=(2,0,0,1).
- Operation 1: Choose (l,r)=(2,3). Now A=(2,0,5,1).
- Operation 2: Choose (l,r)=(3,3). Now A=(2,0,0,1).