AT_arc220_c [ARC220C] Range Increment

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. 1. $ |S| \lt |T| $ and $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ . 2. 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 $ .

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 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 Explanation 1 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) $ . ### 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.