题目描述

在 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

输入 #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. 从 $7$ 向右移动五次到 $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$ 秒。

数据范围

• $1 \leq T \leq 100$。
• 对于最多 9 个测试用例，$K = 10^5$ 且 $Q = 10^5$。
• 其他所有情况下，$2 \leq K \leq 1000$ 且 $1 \leq Q \leq 1000$。
• 字符串 $P$ 的长度为 $K$，且 $P$ 是一个平衡括号字符串，如上所述。
• 对于所有 $j$，$1 \leq S_j \leq K$。
• 对于所有 $j$，$1 \leq E_j \leq K$。

测试集 1（12 分，可见判定）

• 对于所有 $i$，$L_i = 1$。
• 对于所有 $i$，$R_i = 1$。
• 对于所有 $i$，$P_i = 1$。

测试集 2（23 分，隐藏判定）

• 对于所有 $i$，$1 \leq L_i \leq 10^6$。
• 对于所有 $i$，$1 \leq R_i \leq 10^6$。
• 对于所有 $i$，$1 \leq P_i \leq 10^6$。