Given an array, $A$, of $N$ integers, answer $Q$ queries of $2$ types:

1 l_1 r_1 l_2 r_2: Output 1 if the subarray from $[l_1,r_1]$ is identical to $[l_2,r_2]$ or 0 if they are not identical. An array is identical to another if the lengths are equal and the same numbers are present in the same order.

2 i v: Update the integer at index $i$ to $v$.

Constraints

For all subtasks:

$1\le N,Q\le 5\times {10}^5$

$1\le A_i,v\le {10}^9$

$r_1-l_1=r_2-l_2$

$1\le l_1\le r_1\le N$

$1\le l_2\le r_2\le N$

Subtask 1 [20%]

$1\le N,Q\le 5000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain $N$ and $Q$, the number of integers in the array and the number of queries, respectively.

The next line will contain $N$ integers, the array's contents.

The next $Q$ lines will contain one of two queries.

Output Specification

For each query of type $1$, output 1 if the arrays are identical and 0 if they are not.

Sample Input

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

Sample Output

1
1
0