28057번 - Binary Sequence and Queries 서브태스크스페셜 저지다국어

문제

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

1. $p$ $t$: replace $a_p$ with $t$.
2. $l$ $r$ $x$ $y$: Find any $[s, e]$ satisfying the following conditions, or report that none exists:
   • $l \leq s \leq e \leq r$
   • The longest consecutive number of 0ドル$'s in $a_s, a_{s+1}, \ldots, a_e$ is $x$.
   • The longest consecutive number of 1ドル$'s in $a_s, a_{s+1}, \ldots, a_e$ is $y$.

입력

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

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

Followed by $q$ lines, each is in one of the following formats:

• First type query: 1ドル$ $p$ $t$ (1ドル \leq p \leq n, t \in \{0, 1\}$)
• Second type query: 2ドル$ $l$ $r$ $x$ $y$ (1ドル \leq l \leq r \leq n, 0 \leq x, y \leq n$)

출력

For each query of the second type, if there exists a segment $[s, e]$ satisfying the conditions, print two integers $s$ and $e$ separated by a single space. Otherwise, print $-1$.

If there are multiple possible answers, you may print any.

제한

서브태스크

힌트