Coins

There are $N$ coins with possibly different heads probabilities. Toss all $N$ coins. You survive when the number of heads is odd, and you die when it is even.

An initial state is given, followed by $M$ updates. Each update specifies a coin index and its new heads probability. Compare the survival probability against the death probability in each of the $M+1$ states, from the initial state with $0$ updates to the final state with $M$ updates.

The first line contains $N$ and $M$, where $1 \le N \le 500000$ and $0 \le M \le 500000$. The second line contains $N$ real numbers. The $i$-th number is the heads probability of coin $i$. Each of the following $M$ lines contains a coin index and its new probability.

Every probability is at least $0$ and at most $1$, written with up to $6$ digits after the decimal point.

Print $M+1$ lines. Line $i$ holds the answer for the state after $i-1$ updates.

Print "ALIVE" when survival is more likely and "DEAD" when death is more likely. Print "SAME" when the two probabilities are equal.

With heads probabilities $0.3$, $0.4$, and $0.7$, survival has probability $0.516$ and death has probability $0.484$. Survival is more likely.