동전

앞면이 나올 확률이 서로 다른 $N$개의 동전이 있다. $N$개의 동전을 모두 던졌을 때 앞면이 홀수 개이면 살고 짝수 개이면 죽는다.

처음 상태에 이어 확률을 바꾸는 작업이 $M$번 주어진다. 각 작업은 동전 번호와 바뀐 앞면 확률을 지정한다. 확률을 $0$번 바꾼 처음 상태부터 $M$번 바꾼 마지막 상태까지 총 $M+1$개의 상태에서 살 확률과 죽을 확률을 비교한다.

첫 줄에 $N$과 $M$이 주어진다. $1 \le N \le 500000$이고 $0 \le M \le 500000$이다. 둘째 줄에 $N$개의 실수가 주어진다. $i$번째 수는 $i$번 동전의 앞면 확률이다. 이어지는 $M$줄에는 동전 번호와 바뀐 확률이 한 줄에 하나씩 주어진다.

모든 확률은 $0$ 이상 $1$ 이하이며 소수점 아래 $6$자리까지 주어진다.

총 $M+1$줄을 출력한다. $i$번째 줄은 확률을 $i-1$번 바꾼 상태의 답이다.

살 확률이 더 높으면 "ALIVE"를 출력하고 죽을 확률이 더 높으면 "DEAD"를 출력한다. 두 확률이 같으면 "SAME"을 출력한다.

앞면 확률이 $0.3$, $0.4$, $0.7$인 세 동전이 있을 때 살 확률은 $0.516$이고 죽을 확률은 $0.484$이다. 따라서 살 확률이 더 높다.