在 2016 年的 Distributed Code Jam 中，我们为那些偏好更高括号密度的 Lisp 爱好者引入了 Lisp++ 语言。以下是该语言语法的工作原理回顾：
Lisp++ 程序是一个平衡括号字符串。更正式地说，一个 Lisp++ 程序由以下内容之一组成。（在本规范中，$C$ 代表某些程序代码——每次不一定是相同的代码。）
()字面上就是一个左括号和一个右括号。我们称这个(与这个)匹配，反之亦然。(C)一对封闭括号内的程序。我们称这个(与这个)匹配，反之亦然。CC两个程序（不一定是相同的）首尾相连。
今年，我们很高兴发布 Emacs++，这是一个用于 Lisp++ 的文本查看器。Emacs++ 将一个长度为 $K$ 的 Lisp++ 程序显示为一行长字符串，并带有一个你可以移动的光标。光标是一个“块光标”，它总是位于程序中的 $K$ 个字符之一上，而不是位于字符之间。
在任何时候，你可以执行以下三种操作之一来移动光标。（$i$ 代表光标的当前位置，从最左侧位置开始计数，从 1 开始。）
- 将光标向左移动一个字符（如果光标已经在最左侧字符上，则不执行任何操作）。这需要 $L_i$ 秒。
- 将光标向右移动一个字符（如果光标已经在最右侧字符上，则不执行任何操作）。这需要 $R_i$ 秒。
- 将光标传送到与第 $i$ 个字符（即当前光标所在位置的括号）匹配的括号处（如上所述）。这需要 $P_i$ 秒。
我们认为 Emacs++ 对高级用户来说很简单，但我们仍然需要了解它的效率如何。我们有一个 Lisp++ 程序和一系列关于该程序的 $Q$ 个查询；每个查询由一个起始位置 $S_j$ 和一个结束位置 $E_j$ 组成。为了回答第 $j$ 个查询，你必须确定在做出最优决策的情况下，将光标从位置 $S_j$ 移动到位置 $E_j$ 所需的最小可能时间 $N_j$（以秒为单位）。
请输出所有这些 $N_j$ 值的总和。
输入格式
输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $K$（Lisp++ 程序的长度）和 $Q$（查询的数量）。
每个测试用例的第二行包含一个长度为 $K$ 的字符串 $P$，其中每个字符要么是 ( 要么是 )，表示如上所述的 Lisp++ 程序（平衡括号字符串）。
每个测试用例的第三、第四和第五行各包含 $K$ 个整数。这些行中的第 $i$ 个整数分别是上述的 $L_i$、$R_i$ 和 $P_i$ 的值。
每个测试用例的第六和第七行各包含 $Q$ 个整数。这些行中的第 $j$ 个整数分别是上述的 $S_j$ 和 $E_j$。
输出格式
对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是上述 $N_j$ 值的总和。
数据范围
$1 \le T \le 100$。 对于最多 9 个测试用例，$K = 10^5$ 且 $Q = 10^5$。 在所有其他情况下，$2 \le K \le 1000$ 且 $1 \le Q \le 1000$。 $P$ 的长度为 $K$，$P$ 是如上所述的平衡括号字符串。 $1 \le S_j \le K$，对于所有 $j$。 $1 \le E_j \le K$，对于所有 $j$。
测试集 1（可见判定） $L_i = 1$，对于所有 $i$。 $R_i = 1$，对于所有 $i$。 $P_i = 1$，对于所有 $i$。
测试集 2（隐藏判定） $1 \le L_i \le 10^6$，对于所有 $i$。 $1 \le R_i \le 10^6$，对于所有 $i$。 $1 \le P_i \le 10^6$，对于所有 $i$。
样例
输入 1
1 12 5 (()(((())))) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 4 4 12 5 12 11 10 1 6
输出 1
Case #1: 10
说明 1
在样例中，符合测试集 1 的限制，所有时间成本相同（每次移动 1 秒）。 查询的最短时间如下： 1. 从 7 向右移动 5 次到达 12，耗时 5 秒。 2. 从 4 传送到 11，耗时 1 秒。 3. 从 4 传送到 11，然后向左移动到 10，耗时 2 秒。 4. 从 12 传送到 1，耗时 1 秒。 5. 从 5 向右移动到 6，耗时 1 秒。 因此，查询时间的总和为 $5+1+2+1+1 = 10$ 秒。