题目描述

有一棵包含 $2^m-1$ 个结点的完美二叉树。根结点编号为 $1$。对于每个非叶结点 $x$：

• 左儿子的编号为 $2x$；
• 右儿子的编号为 $2x+1$。

每个结点都有一个权值 $a_i$。

一个机器人可以执行以下三种指令：

• U：移动到当前结点的父亲；
• L：移动到当前结点的左儿子；
• R：移动到当前结点的右儿子。

给定一个长度为 $n$ 的指令序列 $s$。机器人从 $1$ 号结点出发，依次执行 $s_1,s_2,\ldots,s_n$。

指令序列 $s$ 的权值，定义为机器人经过的所有结点的权值之和。

注意：

• 同一个结点被经过多次时，其权值也要计算多次；
• 起点和终点都算作经过的结点，因此机器人总共会经过 $n+1$ 个结点。

共有 $q$ 次询问。每次给定两个整数 $l,r$。假设将子串

$$s_l,s_{l+1},\ldots,s_r$$

中的所有字符 L 改为 R，同时将所有字符 R 改为 L，询问修改后的指令序列的权值。

各次询问相互独立，即某次询问所作的修改不会影响之后的询问。

保证每次询问修改后的指令序列都合法，机器人需要到达的结点一定存在。

输入格式

第一行包含三个整数 $n,m,q$，分别表示指令序列长度、二叉树层数和询问次数。

第二行包含 $2^m-1$ 个整数 $a_1,a_2,\ldots,a_{2^m-1}$，表示各结点的权值。

第三行包含一个长度为 $n$ 的字符串 $s$，表示指令序列。

接下来 $q$ 行，每行包含两个整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

样例

9 3 5
1 1 2 3 1 1 0
LRULUURRU
2 4
3 7
1 9
5 8
5 6

13
10
14
14
13

样例解释

对于第 $2$ 个询问，修改后的指令序列为 LRURUULRU，机器人依次经过结点：

$$1,2,5,2,5,2,1,2,5,2.$$

对于第 $3$ 个询问，修改后的指令序列为 RLURUULLU，机器人依次经过结点：

$$1,3,6,3,7,3,1,2,4,2.$$

数据范围与提示

• 对于 $20\%$ 的数据，$n,q\le 5000$；
• 对于 $40\%$ 的数据，$n,q\le 5\times 10^4$；
• 对于另外 $20\%$ 的数据，$n\le 5000$，$m\le 10$；
• 对于另外 $10\%$ 的数据，$s_i\in\{\texttt{U},\texttt{L}\}$；
• 对于全部数据：

$$1\le n\le 10^5, \qquad 1\le m\le 18, \qquad 1\le q\le 10^6,$$$$1\le a_i\le 10^9, \qquad s_i\in\{\texttt{U},\texttt{L},\texttt{R}\}, \qquad 1\le l\le r\le n.$$

保证每次询问修改后的指令序列均合法。