Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Pile of Crabs

By Peregrine_Falcon · Limits 1s, 512 MB

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

You have to observe QQ events.
For each event, a crab numbered XX 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 11. If one’s health is equal to 0, the crab is dead and his value will not get decreased further. If the crab numbered XX is already on the top of the pile, he will not move.
If the crab numbered XX 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 NN and QQ (3N,Q5×105)(3 ≤ N, Q ≤ 5 × 10^5) represents the number of crabs and the number of events respectively.
Each of the next NN lines consists of an integer value HiH_i (1Hi109)(1 ≤ H_i ≤ 10^9) represents the health of ithi^{th}crab for each ii from 11 to NN.

Each of the next QQ lines consists of an integer XX represents the crab that will climb up the pile.

Output

For each of the QQ events, if the crab numbered XX is already dead, print DeadDead in separate lines. Otherwise, do not print anything.

After observing all the events, print a single line with NN integers HiH_ifor each ii from 11 to NNseperated by space. HiH_i represent the health of ithi^{th} crab after all the events.

Samples

InputOutput
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.

InputOutput
10 16
19 5 26 71 16 2 22 8 85 24
8
1
2
1
4
4
9
9
9
5
8
2
6
10
6
9
Dead
Dead
Dead
13 0 24 65 10 0 18 1 78 17

    Discussion

    Statistics


    77% Solution Ratio

    towfiq379Earliest, 7M ago

    MursaleenFastest, 0.2s

    pathanLightest, 11 MB

    MursaleenShortest, 738B

    Submit

    Login to submit

    Editorial

    This problem can be solved using SegmentSegmentSegment TreeTreeTree. First, take an array sized N+Q...

    Related Contests

    Toph uses cookies. By continuing you agree to our Cookie Policy.