편광판

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

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

여러 편광판이 일렬로 놓여 있고, 각 편광판은 $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$는 $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을 한 줄에 하나씩 출력한다.