题目描述

你有一个 $n$ 位的二进制数。

我们将对其进行 $q$ 次操作。每次操作，我们都会是以下三种操作之一：

$1\ i \ j$：将这个数与上 $(2^n-1)⊕(2^i-2^j)$（保证 $i>j$）。

$2\ i\ j$：将这个数或上 $2^i-2^j$（保证 $i>j$）。

$3\ i\ j$：求从低往高第 $i$ 位到第 $j$ 位之间，每一位都相等的区间的最长长度（保证 $i≤j$）。

输入格式

第一行两个正整数 $n,q$。

第二行一个长度为 $n$ 的 $01$ 串，表示这个二进制数。

接下来 $q$ 行，每行三个整数，表示一次询问。

输出格式

对于每个 $3$ 操作，输出一行一个整数表示最长相等区间的长度。

输入样例 1

8 5
10010111
3 3 7
1 3 1
3 1 5
2 7 3
3 3 8

输出样例 1

2
3
5

样例解释

$1$操作后，这个数变成了10010001。

$2$操作后，这个数变成了11111001。

数据范围

下表数据表示数据最大值。