15911번 - 동전

타노스는 N개의 동전을 가지고 있다. 이 동전들은 전부 앞면과 뒷면이 나올 확률이 같은 동전처럼 보이지만, 사실 앞면과 뒷면이 나올 확률이 조금씩 다르다.

타노스는 이제 N개의 동전을 던져서, 앞면이 홀수 개 나온다면 당신을 살려주고, 짝수 개 나온다면 당신을 죽이려고 한다. 잠시 후면 자신의 운명이 결정되지만, 문제 풀이를 좋아하는 당신은 살 확률과 죽을 확률 중 어느 것이 더 높은지를 계산해 보기로 했다.

그런데 타노스가 동전을 던지려다 말고 몇몇 동전의 앞면이 나올 확률을 바꾸는 작업을 M번 반복했다. 당신은 타노스가 어떤 동전을 바꿨는지, 각 동전의 앞면이 나올 확률이 얼마인지를 정확히 알고 있다.

아마도 여러분은 중간에 살 확률이 더 높은 경우가 있었는지, 있었다면 언제였는지가 궁금할 것이다. 동전에 대한 정보와 타노스가 어떤 동전을 어떻게 바꿨는지가 주어지면, 바꾸기 전 상태를 포함해서 총 M+1가지의 상태에서 살 확률과 죽을 확률 중 어느 것이 더 높은지를 계산해야 한다.

첫 줄에 동전의 수 N(1 ≤ N ≤ 500,000)과 확률을 바꾼 횟수 M(0 ≤ M ≤ 500,000)이 주어진다. 다음 줄에 각 동전의 앞면이 나올 확률을 나타내는 실수 N개가 주어진다. 주어진 순서대로 1번 동전부터 N번 동전을 의미한다. 다음 M줄에 타노스가 확률을 바꾼 동전의 번호와 바뀐 확률이 주어진다.

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

M+1개의 줄에 걸쳐 i번째 줄에 확률을 i-1번 바꾼 상태의 답을 출력한다.

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

예제 2에 대해, 살 확률은 51.6%로 죽을 확률인 48.4%보다 높다.