atcoder#AGC006C. [AGC006C] Rabbit Exercise

[AGC006C] Rabbit Exercise

Score : 800800 points

Problem Statement

There are NN rabbits on a number line. The rabbits are conveniently numbered 11 through NN. The coordinate of the initial position of rabbit ii is xix_i.

The rabbits will now take exercise on the number line, by performing sets described below. A set consists of MM jumps. The jj-th jump of a set is performed by rabbit aja_j (2ajN12 \leq a_j \leq N-1). For this jump, either rabbit aj1a_j-1 or rabbit aj+1a_j+1 is chosen with equal probability (let the chosen rabbit be rabbit xx), then rabbit aja_j will jump to the symmetric point of its current position with respect to rabbit xx.

The rabbits will perform KK sets in succession. For each rabbit, find the expected value of the coordinate of its eventual position after KK sets are performed.

Constraints

  • 3N1053 \leq N \leq 10^5
  • xix_i is an integer.
  • xi109|x_i| \leq 10^9
  • 1M1051 \leq M \leq 10^5
  • 2ajN12 \leq a_j \leq N-1
  • 1K10181 \leq K \leq 10^{18}

Input

The input is given from Standard Input in the following format:

NN

x1x_1 x2x_2 ...... xNx_N

MM KK

a1a_1 a2a_2 ...... aMa_M

Output

Print NN lines. The ii-th line should contain the expected value of the coordinate of the eventual position of rabbit ii after KK sets are performed. The output is considered correct if the absolute or relative error is at most 10910^{-9}.

3
-1 0 2
1 1
2
-1.0
1.0
2.0

Rabbit 22 will perform the jump. If rabbit 11 is chosen, the coordinate of the destination will be 2-2. If rabbit 33 is chosen, the coordinate of the destination will be 44. Thus, the expected value of the coordinate of the eventual position of rabbit 22 is 0.5×(2)+0.5×4=1.00.5 \times (-2)+0.5 \times 4=1.0.

3
1 -1 1
2 2
2 2
1.0
-1.0
1.0

xix_i may not be distinct.

5
0 1 3 6 10
3 10
2 3 4
0.0
3.0
7.0
8.0
10.0