There is a pile of crabs standing on one top of another. There are total $N$ crabs numbered $1$ to $N$. The crab numbered $1$ is at the bottom of the pile. Crab numbered $2$ is on top of crab $1$ and so on. The crab numbered $N$ is at the top of the pile. Each crab has an initial health value represented with an integer number.

You have to observe $Q$ events. For each event, a crab numbered $X$ will start climbing from his position to the top of the pile. Every crab he will cross on his way, he will decrease their health value by $1$. If one’s health is equal to 0, the crab is dead and his value will not get decreased further. If the crab numbered $X$ is already on the top of the pile, he will not move. If the crab numbered $X$ is already dead, he will not climb the pile. You have to report the crab is dead.

After observing all the events, you’ve to print the health value of each crab.

Input

The first line on input consists of two integers $N$ and $Q$$(3 ≤ N, Q ≤ 5 × 10^5)$ represents the number of crabs and the number of events respectively. Each of the next $N$ lines consists of an integer value $H_i$$(1 ≤ H_i ≤ 10^9)$ represents the health of $i^{th}$crab for each $i$ from $1$ to $N$.

Each of the next $Q$ lines consists of an integer $X$ represents the crab that will climb up the pile.

Output

For each of the $Q$ events, if the crab numbered $X$ is already dead, print $Dead$ in separate lines. Otherwise, do not print anything.

After observing all the events, print a single line with $N$ integers $H_i$for each $i$ from $1$ to $N$seperated by space. $H_i$ represent the health of $i^{th}$ crab after all the events.

Samples

Input

Output

4 3
2 3 1 4
2
3
1

Dead
2 2 0 2

After the first event, the health of crab 1, 2, 3, and 4 is equal to 2, 3, 0, 3 respectively.

In the second event, we can see crab 3 is already dead. So, it won’t move.

After the third event, the health of crabs 1, 2, 3, and 4 is equal to 2, 2, 0, 2 respectively.