前驱问题

【题目描述】

设 $S$ 是一个由 $0$ 到 $N-1$ 之间的整数组成的集合。请处理以下 $Q$ 个查询：

• 0 $k$：若 $k\notin S$，将 $k$ 插入 $S$；若 $k\in S$，不做任何操作。
• 1 $k$：若 $k\in S$，将 $k$ 从 $S$ 中删除；若 $k\notin S$，不做任何操作。
• 2 $k$：若 $S$ 包含 $k$，输出 $1$；否则输出 $0$。
• 3 $k$：输出大于等于 $k$ 的最小元素（若不存在这样的元素，输出 $-1$）。
• 4 $k$：输出小于等于 $k$ 的最大元素（若不存在这样的元素，输出 $-1$）。

【输入】

$S$ 的初始状态由一个长度为 $N$、仅由 0 和 1 组成的字符串 $T$ 给出。当且仅当 $T_i = 1$ 时，$S$ 包含 $i$。

$N\ Q$
$T$
$c_0\ k_0$
$c_1\ k_1$
$\vdots$
$c_{Q-1}\ k_{Q-1}$

【输出】

按上述规则，对每个类型为 2、3、4 的查询各输出一行其答案。

【输入样例】

6 9
010101
3 3
4 3
4 0
0 4
1 3
2 4
2 3
3 3
4 3

【输出样例】

3
3
-1
1
0
4
1

【数据范围】

• $1 \leq N \leq 10000000$
• $1 \leq Q \leq 1000000$
• $0 \leq k_i \lt N$

【来源】

Library Checker（yosupo06） predecessor_problem