AT_arc220_c.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$.

给你整数 $N,M,K$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。保证 $A$ 的每个元素均在 $0$ 到 $M-1$（含端点）之间。

你可以在整数序列 $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|})$，当且仅当满足下列条件之一。其中 $|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$，使得同时满足：
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$；
   • $S_i$（数值上）小于 $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$

输入从标准输入中按以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例按以下格式给出：

$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.

按测试用例的顺序输出答案，各答案之间用换行符分隔。

对于每个测试用例，输出执行操作后字典序最小的 $A$ 的各个元素，元素之间用空格分隔。

Sample 1 Explanation:
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.

样例 1 解释：
考虑第一个测试用例。

通过执行以下两次操作，我们可以得到 $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)$。

约束条件

• $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$。
• 所有输入值均为整数。