Comeback — Eolymp

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n, q \leq 1 0^{6}$ 1 \leq n, q \leq 10^6) — the size of the arrays and the number of queries.

The second line contains a bit string $a$ of length $n$ .

The third line contains a bit string $b$ of length $n$ .

Each of the next $q$ lines describes a query of one of the following two types:

$t, c, x$ t, c, x where $t = 1$ t = 1, $c \in {a, b}$ c \in \{\textbf{a}, \textbf{b}\}, and $1 \leq x \leq n$ 1 \leq x \leq n — the first type of query.
$t, l_{a}, l_{b}$ t, l_a, l_b where $t = 2$ t = 2, and $1 \leq l_{a}, l_{b} \leq n$ 1 \leq l_a, l_b \leq n — the second type of query.

Output

For each query of type $2$ , output $r_{a}$ r_a and $r_{b}$ r_b on a new line, or $- 1$ $- 1$ if there are no valid right borders.

Examples

Example 1

Loading

Note

For the first query, our subsegments are $[11, 25]$ and $[13, 22]$ . After setting all the other elements to zero, we obtain:

a = [00000000001100100101010000]

a = [00000000001100100101010000]

b = [00000000000001011001110000]

b = [00000000000001011001110000]

Both bit strings have exactly $6$ set bits, and it can be seen that $a$ majorizes $b$ .

Scoring

Here, $Q_{1}$ Q_1 is the number of queries of type $1$ .

( $27$ points): $n, q \leq 100$ n, q \leq 100
( $28$ points): $q \leq 10$ q \leq 10
( $27$ points): $Q_{1} = 0$ Q_1 = 0
( $54$ points): $l_{a} = l_{b}$ l_a = l_b
( $108$ points): $n, q \leq 200000$ n, q \leq 200000
( $56$ points): no additional constraints