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 5\,000~

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