Rabbit Exercise

AtCoder

IDagc006_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ rabbits on a number line. The rabbits are conveniently numbered $1$ through $N$. The coordinate of the initial position of rabbit $i$ is $x_i$. The rabbits will now take exercise on the number line, by performing _sets_ described below. A set consists of $M$ _jumps_. The $j$\-th jump of a set is performed by rabbit $a_j$ ($2≤a_j≤N-1$). For this jump, either rabbit $a_j-1$ or rabbit $a_j+1$ is chosen with equal probability (let the chosen rabbit be rabbit $x$), then rabbit $a_j$ will jump to the symmetric point of its current position with respect to rabbit $x$. The rabbits will perform $K$ sets in succession. For each rabbit, find the expected value of the coordinate of its eventual position after $K$ sets are performed. ## Constraints * $3≤N≤10^5$ * $x_i$ is an integer. * $|x_i|≤10^9$ * $1≤M≤10^5$ * $2≤a_j≤N-1$ * $1≤K≤10^{18}$ ## Input The input is given from Standard Input in the following format: $N$ $x_1$ $x_2$ $...$ $x_N$ $M$ $K$ $a_1$ $a_2$ $...$ $a_M$ [samples]

Samples

Input #1

Output #1

\-1.0
1.0
2.0

Rabbit $2$ will perform the jump. If rabbit $1$ is chosen, the coordinate of the destination will be $-2$. If rabbit $3$ is chosen, the coordinate of the destination will be $4$. Thus, the expected value of the coordinate of the eventual position of rabbit $2$ is $0.5×(-2)+0.5×4=1.0$.

Input #2

Output #2

1.0
-1.0
1.0

$x_i$ may not be distinct.

Input #3

Output #3

0.0
3.0
7.0
8.0
10.0

API Response (JSON)

{
  "problem": {
    "name": "Rabbit Exercise",
    "description": {
      "content": "There are $N$ rabbits on a number line. The rabbits are conveniently numbered $1$ through $N$. The coordinate of the initial position of rabbit $i$ is $x_i$. The rabbits will now take exercise on the ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc006_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ rabbits on a number line. The rabbits are conveniently numbered $1$ through $N$. The coordinate of the initial position of rabbit $i$ is $x_i$.\nThe rabbits will now take exercise on the ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments