28475번 - 편광판

문제

편광판은 빛의 진동 방향을 바꾼다.

빛이 현재 진동하는 방향과 수직한 편광판을 만나면 가로막힌다. 그렇지 않은 경우에는 편광판 방향으로 진동 방향을 바꾸면서 통과한다.

여러 편광판들이 연속해서 있고, 각 편광판은 45ドル$도 단위로 조작할 수 있다.

시작점과 끝점이 주어질 때, 시작점에서 빛을 쏴서 편광판을 모두 통과하여 끝점에 도달할 수 있는지 구하라.

편광판을 통과하기 전의 빛은 모든 방향으로 진동하고 있다.

입력

첫 줄에 편광판의 개수 $N(2 \leq N \leq 200,000円),ドル 쿼리의 개수 $M(1\leq M \leq 200,000円)$이 공백으로 구분되어 주어진다.

두 번째 줄에는 편광판의 초기 상태 $N$개의 정수 $A_i(1 \leq i \leq N; 0 \leq A_i < 8)$가 공백으로 구분되어 주어진다. $A_i$는 편광판이 $(45 \times A_i)$도 방향임을 의미한다.

다음 $M$개의 줄에 걸쳐서 쿼리 $q_i$ $a_i$ $b_i$가 공백으로 구분되어 주어진다. $q_{i}$는 1ドル$ 또는 2ドル$이다.

$q_i$가 1ドル$인 경우 $a_i$번째 편광판을 $(45 \times b_i)$도 방향으로 조작한다는 의미이다. $(1 \leq a_i \leq N; 0 \leq b_i < 8)$

$q_i$가 2ドル$인 경우 $a_i$번째 편광판에 빛을 쐈을 때 $b_i$번째 편광판을 빛이 통과할 수 있는지 묻는다는 의미이다. $(1 \leq a_i < b_i \leq N)$

$q_i=2$인 쿼리는 하나 이상 주어진다.

출력

$q_i=2$인 쿼리에 대해 순서대로, 빛이 편광판을 통과할 수 있다면 1, 아니면 0을 한 줄에 하나씩 출력한다.

제한

힌트