AT_arc220_c [ARC220C] Range Increment

整数 $ 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 $ の長さを表します。 1. $ |S| \lt |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ 。 2. ある整数 $ 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 $ より（数として）小さい。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ。 各テストケースについて、辞書順最小となる操作後の $ A $ の要素を空白区切りで出力せよ。

### Sample Explanation 1 $ 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) $ となる。 ### 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 $ - 全てのテストケースにおける $ N $ の総和は $ 3\times 10^5 $ 以下 - 入力される値は全て整数