시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 104 37 33 41.772%

문제

타노스는 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"을 출력한다.

예제 입력 1

2 3
1.000000 1.000000
1 0.000000
2 0.500000
2 0.000000

예제 출력 1

DEAD
ALIVE
SAME
DEAD

예제 입력 2

3 0
0.300000 0.400000 0.700000

예제 출력 2

ALIVE

힌트

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