City Development

Sociologists have proposed a model to predict the development of cities in a country. The model works as follows.

Suppose, that there are $n$ cities in the country numbered 1 through $n$, and there are $k$ different levels of administrative divisions in this country. City is the lowest level (i.e., the $k$-th level) administrative division. Every $i$-th level administrative division has exactly $n_i$ cities, where $n \bmod n_1 = n_1 \bmod n_2 = \cdots = n_{k-1} \bmod n_k = 0$, and $n_k = 1$. Also, two cities numbered $a$ and $b$ belong to the same $i$-th level administrative division if and only if $\lceil a/n_i \rceil = \lceil b / n_i \rceil$. It is clear that two cities belonging to the same lower level administrative division must belong to the same higher level administrative division.

The model owes the development of a city both to the city itself, and to the mutual interactions between cities. Obviously, the interaction between closer cities is stronger. We introduce the concept of $\textit{lowest common administrative level}$ (LCA for short) to characterize the closeness between two cities. Formally, for two cities numbered $a, b$, $\mathrm{LCA}(a, b)$ is defined as
$$\mathrm{LCA}(a, b) = \max\{i : a, b \text{ belong to the same $i$-th level administrative division}\}$$
In case that city $a$ and $b$ don't belong to any common administrative division, we define $\mathrm{LCA}(a, b) = 0$. Also, we have $\mathrm{LCA}(a, a) = k$. Let $d_t(x)$ denote the development index of the $x$-th city in the $t$-th year, then the model says that
$$ d_{t+1}(x) = \sum_{i = 1}^n \rho_{\mathrm{LCA}(x, i)} d_t(i) $$
where $\rho_i$ $(0 \leq i \leq k)$ is called the interaction coefficient between two cities $a, b$ with $\mathrm{LCA}(a, b) = i$.

Now, given the initial development indexes of all cities, can you use this model to predict the development indexes after $T$ years?

The first line of input consists of only a single integer $K$ $(1 \leq K \leq 20)$, the number of test cases.

Each test case begins with three integers $n, k, T$ $(1 \leq k \leq n \leq 3 \times 10^5, 1 \leq T \leq 10^{18})$, the number of cities, the number of levels of administrative regions, and the number of years, respectively. Then follows a line with $k$ integers $n_1, n_2, \cdots, n_k$ $(1 = n_k \leq n_{k-1} \leq \cdots \leq n_2 \leq n_1 \leq n, n_{i-1} \bmod n_i = n \bmod n_1 = 0)$, the number of cities in each level of administrative divisions. The third line contains $n$ integers $d_0(1), d_0(2), \cdots, d_0(n)$ $(1 \leq d_0(i) \leq 10^6)$, the initial development indexes of the cities. The last line of each test case contains $k+1$ integers, $\rho_0, \rho_1, \cdots \rho_k$ $(1 \leq \rho_0 \leq \rho_1 \leq \cdots \leq \rho_k \leq 10^6)$, the interaction coefficients.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, display a line of $n$ integers, denoting the predicted development indexes of all cities after $T$ years in order. Since the answers might be rather big, you should display these numbers modulo 998244353.

1
4 2 1
2 1
1 3 5 6
2 4 5

39 41 57 58

2018 Multi-University Training Contest 8