你对着面前清一色的 TLE 出了神，你发现你的时限竟然配错了，无奈你剩下能区分的手段已经不多了。

正巧，一年一度的粉兔传火大会就要开始了，粉兔们会依次排成一行进行传火的仪式。

传说传过火炬的粉兔在新的一年都会获得好运，但有的时候有的粉兔会因为各种急事离开座位。

粉免很有可能会在传火大会上进行各种破坏活动。所以在仪式开始之前，你需要对可能发生的紧急情况做一个预演。由于时间是连续的，因此你只需要考察一段连续的区间内可能会发生的紧急情况。

在仪式开始前，并不是所有的粉兔都已经就位。具体来说，有 $n$ 只粉兔排成一行，从左到右依次坐在第 $1\sim n$ 个位置。初始时有一个序列 $a$，只有 $a_i=1$ 的位置 $i$ 上的粉兔已经就座。在这之后会按照预演计划，依次发生 $m$ 个事件。每个事件都形如以下四种之一：

1. 0 p 表示第 $p$ 个位置上的粉兔离开了座位。如果这个位置本来就没有粉兔，那么这个事件发生之后这个位置上仍然没有粉兔。
2. 1 p 表示第 $p$ 个位置上有一只粉兔就座了。如果这个位置本来就有粉兔，那么这个事件发生之后这个位置上仍然有粉兔。
3. ! p 表示第 $p$ 个位置上粉兔的就座情况发生了改变：如果这个位置上先前没有粉兔，就会有一只粉兔在此就座；如果这里本来有一只粉兔，在这之后这个位置上就没有粉兔了。
4. > 兔王高呼“传火”，这个时候如果火炬所在的位置有粉兔，则这一事件之后火炬所处的位置变为当前位置的下一个位置，否则火炬不动。当然下一个位置有可能不存在，此时称这个位置为第 $n+1$ 个位置。

初始时火炬在第 $1$ 个位置上。经过一系列事件以及传火的尝试后，火炬最后会处在某一个位置上。

由于需要预演紧急情况，兔王提出了 $q$ 个问题，其中每个问题形如 $l,r$，表示如果第 $l$ 到第 $r$ 个事件依次发生（且仅发生这些事件），火炬最后应该在哪个位置上。你需要依次回答这 $q$ 个问题。当然由于这是排练，因此每一次预演之间都是互不影响的。

输入格式

第一行一个字符 $\text{A}$ 或者 $\text{B}$ 表示数据类型。在本题中，你需要针对两种不同的情况分别设计算法。

第二行三个整数 $n,m,q$ 与题目对应，分别表示粉兔的个数，事件的个数和询问的个数。

第三行一个 $01$ 串，表示初始的就座情况：第 $i$ 个位置为 $1$ 表示第 $i$ 个位置上初始有粉兔，否则表示没有。

接下来 $m$ 行每行一个操作，形如以下四种格式之一：

• 0 p 表示第 $p$ 个位置上的粉兔离开座位；
• 1 p 表示第 $p$ 个位置上的粉兔回到座位；
• ! p 表示第 $p$ 个位置上的粉兔就座状态发生改变；
• > 表示一次传火的尝试。

再接下来 $q$ 行，每行两个整数 $l,r$，表示对 $[l,r]$ 中的事件进行预演。

输出格式

共 $q$ 行每行一个整数，表示每次预演最后火炬传递到了哪个位置。

样例一

input

A
2 5 5
00
1 1
>
>
1 2
>
1 1
1 2
1 3
1 4
1 5

output

1
2
2
2
3

样例二

input

B
4 20 20
1011
>
0 1
>
1 1
>
1 3
>
0 2
! 2
>
>
>
! 3
0 4
0 4
>
>
1 3
0 1
>
1 10
5 15
2 11
14 15
13 14
11 18
6 18
2 16
10 13
4 5
13 20
15 19
3 11
12 18
13 15
5 8
16 17
16 19
3 20
2 14

output

3
5
4
1
1
2
5
5
2
2
2
2
4
2
1
2
2
2
5
5

样例三

见附件下载。该样例满足子任务 1,3 的限制。

样例四

见附件下载。该样例满足子任务 2,3 的限制。

样例五

见附件下载。该样例满足子任务 3 的限制。

样例六

见附件下载。该样例满足子任务 4,5 的限制。

样例七

见附件下载。该样例满足子任务 5 的限制。

数据范围与提示

本题有两种数据类型：$\text{A}$ 和 $\text{B}$。

子任务 $1,2,3$ 属于数据类型 $\text{A}$。对于属于类型 $\text{A}$ 的所有数据，保证 $1\le n\le 2\times {10}^5$，$1\le m,q\le {10}^6$。所有 $a_i$ 均为 $0$。不存在 ! 操作。以下是子任务 $1,2,3$ 的具体情况及特殊性质：

子任务 $4,5$ 属于数据类型 $\text{B}$。对于属于类型 $\text{B}$ 的所有数据，保证 $1\le n,m,q\le 2\times {10}^5$。以下是子任务 $4,5$ 的具体情况及特殊性质：

对于所有数据，$a_i\in \{0,1\}$，${\text{op}}_i\in \{$0$,$1$,$!$,$>$\}$，$1\le p\le n$，$1\le l\le r\le m$。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$