有 $N$ 个骑士，编号从 $1$ 到 $N$，按顺序站成一排。第 $i$ 个骑士的战斗力为 $P_i$。

这些骑士将参加一场马上长枪比武。为此，每个骑士会将剑指向左或右。若 $S_i = 0$，则第 $i$ 个骑士将剑指向左；若 $S_i = 1$，则指向右。其中 $S$ 是一个长度为 $N$ 的二进制字符串。

一次比武（joust）定义如下过程：

1. 初始时所有骑士均存活。
2. 设 $A$ 为当前仍然存活的骑士编号按从小到大排列组成的列表，$m$ 为 $A$ 的大小。
3. 对于每个 $i$ 从 $1$ 到 $m$，若编号为 $A_i$ 的骑士存在一个相邻骑士，其战斗力更高且该相邻骑士的剑正指向 $A_i$，则将骑士 $A_i$ 标记为死亡。形式化地，若以下任一条件成立，则骑士 $A_i$ 被标记为死亡：
   • $i - 1 > 0$ 且 $P_{A_{i-1}} > P_{A_i}$ 且 $S_{A_{i-1}} = 1$
   • $i + 1 \le m$ 且 $P_{A_{i+1}} > P_{A_i}$ 且 $S_{A_{i+1}} = 0$
4. 若在 $A$ 中至少有一名骑士被标记为死亡，则返回步骤 2。

现在给出 $Q$ 次询问，每次询问的形式为：

• 给定一个整数 $x$（$1 \le x \le N$），将 $S_x$ 修改为 $1 - S_x$。

在每次询问之后，计算进行一次比武后仍然存活的骑士数量。

注意：每次比武结束后，骑士不会保持死亡状态（即每次询问都是在初始全部存活的情况下重新进行比武）。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$（$1 \le N, Q \le 10^6$）——数组 $P$ 的大小以及询问次数。

第二行包含 $N$ 个空格分隔的整数 $P_1, P_2, \dots, P_N$（$1 \le P_i \le N$）。

第三行包含一个长度为 $N$ 的二进制字符串 $S$。

接下来 $Q$ 行，每行包含一个整数 $x$（$1 \le x \le N$），表示将 $S_x$ 修改为 $1 - S_x$ 的一次询问。

输出格式

输出 $Q$ 行，第 $i$ 行输出一个整数 $q_i$，表示第 $i$ 次询问后进行一次比武后存活的骑士数量。

子任务

• 子任务 1（6 分）：$N, Q \le 500$
• 子任务 2（9 分）：对所有 $1 \le i < N$，有 $P_i \le P_{i+1}$
• 子任务 3（17 分）：当 $i \ne j$ 时，$P_i \ne P_j$，且每次询问的答案保证不超过 $50$
• 子任务 4（19 分）：当 $i \ne j$ 时，$P_i \ne P_j$
• 子任务 5（19 分）：$N, Q \le 10000$
• 子任务 6（30 分）：无额外限制

样例数据

样例 1

输入

5 3
2 1 3 4 3
11011
1
3
4

输出

2
4
2

样例 2

输入

10 5
10 1 2 3 8 9 4 5 7 6
0111100110
10
5
6
5
1

输出

5
5
3
6
1

说明

在第一个样例中，第一次询问后，$S$ 变为 $01011$。

• 初始存活骑士编号为 ${1, 2, 3, 4, 5}$。
• 第一轮后，剩余骑士为 ${1, 3, 4}$。
• 第二轮后，剩余骑士为 ${3, 4}$。
• 第三轮没有新的骑士死亡，因此最终有 $2$ 名骑士存活。

第二次询问后，$S$ 变为 $01111$。

• 第一轮后，剩余骑士为 ${2, 3, 4, 5}$。
• 第二轮没有新的骑士死亡，因此最终有 $4$ 名骑士存活。