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.