Coins

Time limit2sMemory limit512 MB

Summary

Maintain the probability that the number of heads among N coins is odd, under M point updates to individual coin probabilities, and report which outcome is more likely after each update.

Level: Medium7 of 10
Topics: Math, Probability, Dynamic programming, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Hint

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.

Examples2

Example 1

Input

2 3
1.000000 1.000000
1 0.000000
2 0.500000
2 0.000000

Expected output

DEAD
ALIVE
SAME
DEAD

Example 2
Input
```
3 0
0.300000 0.400000 0.700000
```
Expected output
```
ALIVE
```