I. Permutation Online
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alex like math, and permutations are math. So he made a problem about permutations.

A permutation is a sequence of integers from $$$1$$$ to $$$N$$$ of length $$$N$$$ containing each number exactly once. You are given a permutation $$$p_1, p_2 \dots p_N$$$, and another list of integers $$$w_1, w_2 \dots w_K$$$.

For $$$1 \leq i \leq N$$$, and $$$1 \leq j \leq K$$$, define $$$a_{i, j} = k$$$ if $$$k$$$ is the $$$j$$$th largest index among those satisfying $$$p_k \gt p_i$$$ and $$$k \lt i$$$. If fewer than $$$j$$$ such indices satisfy the condition, $$$a_{i, j} = 0$$$.

For each index $$$1 \leq i \leq N$$$, please find $$$\sum_{j = 1}^K a_{i, j} w_j$$$.

For some test cases, you will need to process the permutation online. You must answer all the indices in order, and you won't know later values of the permutation until you've answered all the earlier indices.

Input

The first line contains three integers, $$$N$$$, $$$K$$$, and $$$O$$$, $$$1 \leq N, K \leq 10^6$$$, $$$1 \leq NK \leq 10^8$$$, and $$$0 \leq O \leq 1$$$.

The second line contains $$$K$$$ integers, $$$w_1, w_2, \dots w_K$$$, $$$1 \leq w_i \leq 10^6$$$ for all $$$1 \leq i \leq K$$$.

The third line contains $$$N$$$ integers.

If $$$O = 0$$$, this line contains $$$p_1, p_2, \dots p_N$$$.

If $$$O = 1$$$, this line contains $$$x_1, x_2 \dots x_N$$$, $$$1 \leq x_i \leq N$$$. The permutation is encrypted to ensure you process it online.

To decrypt $$$p_i$$$, use the formula

$$$$$$p_i = ((x_i + ans_{i-1})\mod N) + 1$$$$$$.

Where $$$ans_0 = 0$$$. Compute $$$p_1$$$, then find $$$ans_1$$$, then use $$$ans_1$$$ to compute $$$p_2$$$, and so on. —

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1−8$$$ satisfy $$$O = 0$$$.

Tests $$$9-20$$$ satisfy $$$O = 1$$$.

Tests $$$1-2$$$ and $$$9$$$ satisfy $$$N \leq 5000$$$, other tests satisfy no other constraints on $$$N$$$.

Tests $$$3-6$$$ and $$$10$$$ satisfy $$$K = 1$$$, other tests satisfy no other constraints on $$$K$$$.

Output

$$$N$$$ space-separated integers, representing the answer for each index from $$$1 \dots N$$$.

Examples
Input
5 2 0
1 10
5 2 4 1 3
Output
0 1 1 23 13
Input
5 2 1
1 10
4 1 2 4 4
Output
0 1 1 23 13
Note

In the first sample,

For $$$i = 1$$$, there are no indices $$$k$$$ satisfying $$$p_k \gt p_1$$$ and $$$k \lt 1$$$. Therefore $$$a_{1,1} = 0$$$ and $$$a_{1,2} = 0$$$, so the answer is $$$0 \cdot 1 + 0 \cdot 10 = 0$$$.

For $$$i = 2$$$, $$$k = 1$$$ is the only index satisfying $$$p_k \gt p_2$$$ and $$$k \lt 2$$$. Therefore $$$a_{2,1} = 1$$$ and $$$a_{2,2} = 0$$$, so the answer is $$$1 \cdot 1 + 0 \cdot 10 = 1$$$.

For $$$i = 3$$$, $$$k = 1$$$ is the only index satisfying $$$p_k \gt p_3$$$ and $$$k \lt 3$$$. Therefore $$$a_{3,1} = 1$$$ and $$$a_{3,2} = 0$$$, so the answer is $$$1 \cdot 1 + 0 \cdot 10 = 1$$$.

For $$$i = 4$$$, $$$k = 3, 2, 1$$$ are indices satisfying $$$p_k \gt p_4$$$ and $$$k \lt 4$$$. Therefore $$$a_{4,1} = 3$$$ and $$$a_{4,2} = 2$$$, so the answer is $$$3 \cdot 1 + 2 \cdot 10 = 23$$$. Note that even though $$$k = 1$$$ satisfies the condition, it is not used in the answer as $$$K = 2$$$, so only the 2 largest values of $$$k$$$ matter.

For $$$i = 5$$$, $$$k = 3, 1$$$ are indices satisfying $$$p_k \gt p_5$$$ and $$$k \lt 5$$$. $$$a_{5,1} = 3$$$ and $$$a_{5,2} = 1$$$, so the answer is $$$3 \cdot 1 + 1 \cdot 10 = 13$$$.

The second sample has the same values of $$$p$$$ as the first sample, but it is encrypted.

—

Problem Idea: Alex_C

Problem Preparation: Alex_C

Occurrences: Advanced I