AT_aalc001_q.Number of Moves

给定正整数 $N,M,Q$、一个长度为 $N$ 的由字符 0 和 1 组成的字符串 $S$，以及一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。

你需要处理 $Q$ 个查询。每个查询属于以下两种类型之一：

• 1 i：将字符串 $S$ 的第 $i$ 个字符 $S_i$ 翻转（即若为 0 则变为 1，若为 1 则变为 0）。
• 2 x l r：执行如下过程，并求最终获得的钱数：
  • 你从数轴上坐标为 $x$ 的位置出发，初始持有 $0$ 日元。
  • 按照 $i=l,l+1,\ldots,r$ 的顺序，对每个 $i$ 执行以下操作：
    • 若 $S_i$ 为 0，则面向负方向；若 $S_i$ 为 1，则面向正方向。
    • 重复执行以下操作 $A_i$ 次：
      • 若你当前面向的方向上，前方 $1$ 单位处的坐标在区间 $[0, M]$ 内（含端点），则移动到该坐标，并获得 $1$ 日元；否则保持当前位置，钱数不变。

对于每个类型 2 的查询，请从指定的起始坐标 $x$ 出发，以 $0$ 日元开始执行上述过程，且不同查询之间不继承位置或钱数。

输入从标准输入中按以下格式给出：

$N$ $M$ $Q$
$S$
$A_1$ $A_2$ $\ldots$ $A_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询以如下两种格式之一给出：

$1$ $i$

$2$ $x$ $l$ $r$

设 $q$ 为类型 $2$ 的查询次数。输出 $q$ 行，其中第 $j$ 行应包含针对第 $j$ 个类型 $2$ 查询，在执行完相应操作后你所拥有的钱数。

样例 1 解释：
对于第 $1$ 个查询，从坐标 $5$ 出发，依次尝试向正方向、负方向、正方向、负方向、负方向移动。各阶段结束后的坐标依次为 $9,1,4,0,0$，共获得 $19$ 日元。

对于第 $3$ 个查询，从坐标 $5$ 出发，依次尝试向正方向、正方向、正方向、负方向、负方向移动。各阶段结束后的坐标依次为 $9,10,10,4,2$，共获得 $13$ 日元。

限制条件

• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $S$ 是一个长度为 $N$ 的字符串，仅由字符 0 和 1 组成。
• $1 \le A_i \le 10^9$
• 对于类型 $1$ 的查询，满足 $1 \le i \le N$
• 对于类型 $2$ 的查询，满足 $0 \le x \le M$，$1 \le l \le r \le N$
• 输入中的所有数值均为整数。