Problem Description

This problem contains multiple test cases.

Given a large number in base $k$ with $n$ digits.

Let $S(l,r)$ denote the new number in base $k$ formed by taking the digits from the $l$-th to the $r$-th position from the highest to the lowest in the given large number.

You need to find the sum $\sum\limits_{1\leq l\leq r\leq n} S(l,r)$, with the sum also calculated in base $k$.

Since the answer may be very large, let $x$ be the base $k$ representation of $(20070720)_{10}$, you only need to output the result modulo $x$.

Reminder: All sums, operations, and values are based in base $k$.

Input Format

The first line contains an integer $T$, indicating the number of test cases.

For each test case, the first line contains two positive integers $n$ and $k$, representing the large number.

The second line of each test case contains an array $a$, listing the digits of the large number from the highest to the lowest position. It is guaranteed that $\forall i\in[1,n], 0\leq a_i<k$.

Output Format

For each test case, output one line representing the result modulo $x$. Since this is also a number in base $k$, output each digit separated by a space.

Note that your output should not contain leading zeros.

Sample Input and Output

Sample Input #1

1
3 2
1 1 0

Sample Output #1

1 1 0 1

Sample Input #2

1
2 20070721
20070720 1

Sample Output #2

2

Notes

Explanation of Sample #1

All possible $S(l,r)$: $(1)_2, (1)_2, (0)_2, (11)_2, (10)_2, (110)_2$. Adding them in base $2$ gives $(1101)_2$, and taking modulo $(20070720)_{10} = (1001100100100000101000000)_2$ results in $(1101)_2$.

Explanation of Sample #2

For this number, $S(1,1)$ is divisible by $(\overline{20070720})_{20070721}$, and both $S(2,2)$ and $S(1,2)$ leave a remainder of $1$ when divided by $(\overline{20070720})_{20070721}$. Thus, the result modulo $(\overline{20070720})_{20070721}$ is $(2)_{20070721}$.

Data Range

This problem has subtask bundling and dependency.

For $100\%$ of the data, $1\leq T\leq 10$, $1\leq n\leq 5\times 10^5$, $0\leq a_i<k\leq 10^9$, $2\leq k\leq 10^9$. The large number in base $k$ may contain leading zeros.

见题面 Input 部分

见题面 Output 部分