You are given a binary sequence $a_1, a_2, \ldots, a_n$ of length $n$. Process $q$ queries of two different types:

• "`1 $p$ $t$` ": replace $a_p$ with $t$.
• "`2 $\ell$ $r$ $x$ $y$` ": find any segment $[s, e]$ satisfying the following conditions, or report that there is no such segment:
  • It is a subsegment of $[\ell, r]$. Formally, $\ell \leq s \leq e \leq r$.
  • The longest consecutive segment of $0$s in the sequence $a_s, a_{s+1}, \ldots, a_e$ has length $x$.
  • The longest consecutive segment of $1$s in the sequence $a_s, a_{s+1}, \ldots, a_e$ has length $y$.

Input

The first line contains two integers: $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^5$).

The second line contains a binary string of length $n$ denoting the binary sequence $a_1 a_2 \ldots a_n$.

Then follow $q$ lines. Each of them is in one of the following formats:

• First query format: "`1 $p$ $t$` " ($1 \leq p \leq n$, $t \in \{0, 1\}$).
• Second query format: "`2 $\ell$ $r$ $x$ $y$` " ($1 \leq \ell \leq r \leq n$, $0 \leq x, y \leq n$).

Output

For each query of the second type, print the answer on a separate line:

• If there exists a segment $[s, e]$ satisfying the conditions, print two integers $s$ and $e$.
• Otherwise, print $-1$.

If there are multiple possible answers, print any one of them.

Examples

Input 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

Output 1

2 3
-1
1 3
1 4

Input 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

Output 2

-1
-1
-1
1 1
-1