Problem Description

This problem contains multiple test cases.

You are given an $n$-digit base-$k$ big number.

Let $S(l,r)$ denote the new base-$k$ number formed by taking the digits from the $l$-th to the $r$-th digit (from most significant to least significant) of this base-$k$ number.

You need to compute $\sum\limits_{1\leq l\leq r\leq n} S(l,r)$. Note that this summation is also done in base $k$.

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

Reminder again: all summations, operations, and modulo in this problem are done in base $k$.

Input Format

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

For each test case, the first line contains two positive integers $n,k$, describing this big number.

The second line of each test case contains a sequence $a$, which gives each digit of this base-$k$ big number from most significant to least significant. It is guaranteed that $\forall i\in[1,n],0\leq a_i<k$.

Output Format

For each test case, output one line: the answer modulo $x$. Since it is also a base-$k$ number, output each digit in order separated by spaces.

Note that your output should not contain leading zeros.

1
3 2
1 1 0

1 1 0 1

1
2 20070721
20070720 1

2

Hint

Explanation for Sample #1

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

Explanation for Sample #2

For this number, $S(1,1)$ is clearly divisible by $(\overline{20070720})_{20070721}$. After dividing $S(2,2)$ and $S(1,2)$ by $(\overline{20070720})_{20070721}$, both remainders are $1$. Therefore, the answer after modulo is $(2)_{20070721}$.

Constraints

This problem uses bundled subtasks and subtask dependencies.

For $100\%$ of the testdata, $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 base-$k$ big number may contain leading zeros.

Translated by ChatGPT 5