U397404 【模板】括号匹配

小 K 不喜欢括号匹配题。

于是小 K 把这个难题丢给了你： 我们称一个字符串是合法匹配，当且仅当如下情况： 1. 空串是合法匹配； 2. `()` 或 `[]` 是合法匹配； 3. 当 `A` 是合法匹配时，`(A)` 或 `[A]` 是合法匹配； 4. 当 `A` 和 `B` 都是合法匹配时，`AB` 是合法匹配。 现在小 K 给了你一个长度为 $n$ 的字符串 $s$ 和 $q$ 次询问。 每次询问查询 $s[l...r]$ 是否为合法匹配。其中，$s[l...r]$ 表示字符串 $s$ 中第 $l$ 个字符到第 $r$ 个字符顺序连接形成的子串。

第一行两个正整数 $n, q$，含义见题目。 第二行一个长度为 $n$ 的字符串 $s$。 接下来 $q$ 行，每行两个正整数 $l, r$，表示询问 $s[l...r]$ 是否为合法匹配。

输出每次询问的结果，换行隔开。如果 $s[l...r]$ 是合法匹配，输出 `Yes`，否则输出 `No`。

对于 $30\%$ 的数据，$n, q \le 100$。 对于 $70\%$ 的数据，$n, q \le 10^5$。 对于 $100\%$ 的数据，$1 \le n, q \le 10^6$，$1 \le l \le r \le n$，$s$ 中每个字符必定是 `(`、`)`、`[`、`]` 之一。