给定一个长度为 $n$ 的二进制序列 $a_1, a_2, \ldots, a_n$。处理 $q$ 次以下两种类型的询问：

• 1 $p$ $t$：将 $a_p$ 替换为 $t$。

• 2 $\ell$ $r$ $x$ $y$：寻找任意一个满足以下条件的区间 $[s, e]$，如果不存在这样的区间，则报告无解：

  • 它是 $[\ell, r]$ 的子区间。形式化地，$\ell \leq s \leq e \leq r$。
  • 序列 $a_s, a_{s+1}, \ldots, a_e$ 中最长连续 $0$ 的长度为 $x$。
  • 序列 $a_s, a_{s+1}, \ldots, a_e$ 中最长连续 $1$ 的长度为 $y$。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$）。

第二行包含一个长度为 $n$ 的二进制字符串，表示二进制序列 $a_1 a_2 \ldots a_n$。

接下来 $q$ 行，每行采用以下格式之一：

• 第一种询问格式：1 $p$ $t$（$1 \leq p \leq n$，$t \in \{0, 1\}$）。
• 第二种询问格式：2 $\ell$ $r$ $x$ $y$（$1 \leq \ell \leq r \leq n$，$0 \leq x, y \leq n$）。

输出格式

对于每个第二种类型的询问，在单独的一行中输出答案：

• 如果存在满足条件的区间 $[s, e]$，输出两个整数 $s$ 和 $e$。
• 否则，输出 $-1$。

如果有多个可能的答案，输出其中任意一个。

样例

输入样例 1

4 6
0010
2 1 4 1 1
1 3 0
2 1 4 1 1
2 1 4 3 0
1 4 1
2 1 4 3 1

输出样例 1

2 3
-1
1 3
1 4

输入样例 2

1 6
1
2 1 1 0 0
2 1 1 1 0
2 1 1 1 1
1 1 0
2 1 1 1 0
2 1 1 0 1

输出样例 2

-1
-1
-1
1 1
-1