도서관 서가 정리 게임

문제

도서관에 서가 N개가 한 줄로 놓여 있고, i번 서가에는 책이 a_i권 꽂혀 있다. 두 사서가 심심풀이로 번갈아 가며 책 정리 게임을 한다. 게임을 시작하기 전에 구간 [l, r]을 정하며, 그 게임에서는 l번부터 r번까지의 서가만 사용한다. 자기 차례가 된 사서는 사용 가능한 서가 중 책이 한 권 이상 남은 서가 하나를 골라, 그 서가에서 책을 정확히 2의 거듭제곱 권(1, 2, 4, 8, ...)만큼 치워야 한다. 서가에 남은 책보다 많은 권수는 치울 수 없다. 자기 차례에 아무 서가에서도 책을 치울 수 없는 사서가 게임에서 진다. 두 사서는 모두 최선을 다한다. 서가의 책 수는 시간이 지나며 바뀐다. 다음 두 종류의 사건이 총 Q개 순서대로 주어진다. 1 i x : i번 서가의 책 수를 x권으로 바꾼다. 2 l r : l번부터 r번까지의 서가만 사용해 게임을 새로 시작한다고 할 때, 먼저 시작하는 사서가 이기는지 판정한다. 이 사건은 서가 상태를 바꾸지 않는다. 2번 사건마다 결과를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 서가 수 N과 사건 수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 a_1, ..., a_N이 주어진다. (0 ≤ a_i ≤ 10^9, 정수) 이어서 Q개의 줄에 사건이 하나씩 주어진다. 1번 사건은 "1 i x" (1 ≤ i ≤ N, 0 ≤ x ≤ 10^9), 2번 사건은 "2 l r" (1 ≤ l ≤ r ≤ N) 형식이다. 2번 사건이 적어도 하나 존재한다.

출력

2번 사건마다 한 줄에 하나씩, 먼저 시작하는 사서가 이기면 FIRST, 지면 SECOND를 출력한다.

5 5
3 4 5 1 2
2 1 5
2 2 3
1 3 4
2 2 3
2 4 4

SECOND
FIRST
SECOND
FIRST

1 3
0
2 1 1
1 1 7
2 1 1

SECOND
FIRST

출처: Devin.KR 자체 제작