급식 트레이 게임

문제

학교 급식실에는 N개의 배식 줄이 있고, i번 줄에는 반찬이 a_i 개 쌓여 있다. 두 학생이 번갈아 가며 반찬을 가져가는 놀이를 한다. 자기 차례에는 반찬이 남아 있는 줄 하나를 골라 그 줄에서 1개 이상 k_i 개 이하의 반찬을 가져가야 한다. 단, 그 줄에 남은 반찬 수보다 많이 가져갈 수는 없다. 더 이상 가져갈 반찬이 어떤 줄에도 없어 움직일 수 없는 학생이 진다. 두 학생은 항상 최선을 다한다. 급식 도우미는 Q개의 일을 차례로 처리한다. 첫 번째 종류의 일은 i번 줄의 반찬 수를 x개로 바꾸는 것이다. 두 번째 종류의 일은 l번 줄부터 r번 줄까지만 사용해서 놀이를 새로 시작한다고 할 때 먼저 시작하는 학생이 이기는지 알아보는 것이다. 이때 l번 줄부터 r번 줄까지의 줄만 놀이에 쓰이며, 각 줄의 현재 반찬 수와 k_i 를 그대로 따른다. 두 번째 종류의 일은 현재 반찬 수를 바꾸지 않으며, 각 질문은 서로 독립적이다. 두 번째 종류의 일마다 먼저 시작하는 학생이 이기면 First, 지면 Second 를 출력하라.

입력

첫째 줄에 N과 Q(1 ≤ N, Q ≤ 200,000)가 공백으로 구분되어 주어진다. 둘째 줄에 a_1, ..., a_N(0 ≤ a_i ≤ 10^9)이 주어진다. 셋째 줄에 k_1, ..., k_N(1 ≤ k_i ≤ 10^9)이 주어진다. 이어지는 Q개의 줄에 일이 하나씩 주어진다. 첫 번째 종류는 `1 i x`(1 ≤ i ≤ N, 0 ≤ x ≤ 10^9) 형식이고, 두 번째 종류는 `2 l r`(1 ≤ l ≤ r ≤ N) 형식이다. 두 번째 종류의 일이 적어도 하나 있다고 보장하지는 않는다.

출력

두 번째 종류의 일마다 한 줄씩, 먼저 시작하는 학생이 이기면 First, 지면 Second 를 출력한다. 두 번째 종류의 일이 없으면 아무것도 출력하지 않는다.

5 4
5 3 7 2 4
2 1 3 1 4
2 1 3
2 1 5
1 3 8
2 2 3

Second
First
First

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

Second
First

출처: Devin.KR 자체 제작