405963: GYM102192 C 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 , and n_k = 1. Also, two cities numbered a and b belong to the same i-th level administrative division if and only if ⌈ a / n_i⌉ = ⌈ b / n_i⌉. 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 lowest common administrative level (LCA for short) to characterize the closeness between two cities. Formally, for two cities numbered a, b, is defined as

In case that city a and b don't belong to any common administrative division, we define . Also, we have . Let d_t(x) denote the development index of the x-th city in the t-th year, then the model says that

where ρ_i (0 ≤ i ≤ k) is called the interaction coefficient between two cities a, b with .

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 ≤ K ≤ 20), the number of test cases.

Each test case begins with three integers n, k, T (1 ≤ k ≤ n ≤ 3 × 10⁵, 1 ≤ T ≤ 10¹⁸), 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₁, n₂, ..., n_k , the number of cities in each level of administrative divisions. The third line contains n integers d₀(1), d₀(2), ..., d₀(n) (1 ≤ d₀(i) ≤ 10⁶), the initial development indexes of the cities. The last line of each test case contains k + 1 integers, ρ₀, ρ₁, ... ρ_k (1 ≤ ρ₀ ≤ ρ₁ ≤ ... ≤ ρ_k ≤ 10⁶), the interaction coefficients.

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

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