408052: GYM102968 B Rainbow Array

At AGM we love colors, as every problem has a unique color. Being passionate about rainbows, you noticed that the spectrum indicator of a rainbow is equal to $$$D$$$.

You are given an array of colors (each color is a non-negative integer value). A sequence of colors is called a $$$rainbow\ sequence$$$ if the sum of its colors is divisible by $$$D$$$. Every time you look at the array you want to see a $$$rainbow\ sequence$$$ of colors. Because your visibility area is not that large, at some point, you can look at exactly $$$K$$$ consecutive positions from the array.

For each position $$$i$$$ in the array, it costs you $$$cost_i$$$ to change the color from that position to any other color (any other non-negative integer value). You have to answer $$$Q$$$ queries. For every query, you are given a position $$$pos$$$ from the array and you need to find out the minimum total cost to change the array, so that each subsequence of length $$$K$$$ (each sequence of $$$K$$$ consecutive positions from the array) becomes a $$$rainbow\ sequence$$$, but you can not change the color from the position $$$pos$$$.

The first line of the input contains $$$3$$$ integers: $$$2 \leq N \leq 500.000$$$, the length of the array of colors; $$$2 \leq K \leq min(100, N)$$$, your visibility area length; and $$$1 \leq D \leq 500$$$, the spectrum indicator of a rainbow.

The second line contains the array $$$col$$$ of length $$$N$$$, the array of colors, $$$1 \leq col_i \leq 10^9$$$.

The third line contains the array $$$cost$$$ of length $$$N$$$, $$$cost_i$$$ being the cost of changing the color from position $$$i$$$ to any other color, $$$1 \leq cost_i \leq 10^9$$$.

The fourth line contains one integer $$$Q$$$, representing the number of queries, $$$1 \leq Q \leq 500.000$$$.

Each of the following $$$Q$$$ lines contains one integer $$$1 \leq pos_i \leq N$$$ , the position that can not be changed for this particular query.

The output should contain $$$Q$$$ integers, each on a separate line, representing the minimum cost for each query.

7 3 5
5 10 3 15 20 8 2
2 2 3 2 3 3 4
2
5
4

4
9

14 4 7
2 8 10 13 6 8 10 22 25 3 11 13 12 21
1 1 1 1 1 1 1 1 1 1 1 1 1 1
5
8
5
2
7
13

8
9
7
7
8

The first example:

For the first query we can not change the position 5. A solution would be to change the color on the position 1 to $$$7$$$, and the color on the position 4 to $$$12$$$. The resulting array will be (7, 10, 3, 12, 20, 8, 2), in which all subsequences of length 3 have the sum of the elements divisible by 5. The cost of these changes is 2 + 2 = 4. This is the minimum possible cost.

For the second query we can not change the position 4. A solution would be to change the color on the position 7 to $$$10$$$, the color on the position 2 to $$$12$$$, and the color on the position 5 to $$$22$$$. The resulting array will be (5, 12, 3, 15, 22, 8, 10), in which all subsequences of length 3 have the sum of the elements divisible by 5. The cost of these changes is 4 + 2 + 3 = 9. This is the minimum possible cost.