考虑以下罗马数字的推广。总共有 $n$ 个数码，每个数码都有自己的优先级和数值。在本题中，我们用由大小写英文字母组成的字符串来表示这些数码。我们分别用 $p_i$、$v_i$ 和 $d_i$ 表示第 $i$ 个罗马数码的优先级、数值和字符串表示。

一个罗马数字是由罗马数码组成的数组。一个数字 $d_1 \dots d_m$ 的值是递归计算的。首先，选择一个位置 $i$，使得数码 $d_i$ 具有最高的优先级。如果存在多个具有最高优先级的数码，选择其中位置 $i$ 最小的一个。然后：

$$\text{value}(d_1 \dots d_m) = v_i - \text{value}(d_1 \dots d_{i-1}) + \text{value}(d_{i+1} \dots d_m)$$

其中 $v_i$ 是 $d_i$ 的数值。空数字的值约定为 $0$。

例如，考虑以下三元组 $(p_i, v_i, d_i)$：$(1, 1, \text{I})$、$(2, 5, \text{V})$ 和 $(3, 10, \text{X})$。它们为常见的罗马数字赋予了通常的值：例如，$\text{value}(\text{II}) = 2$，$\text{value}(\text{IX}) = 9$，以及 $\text{value}(\text{XIV}) = 14$。另一方面，此时的表示并不是唯一的：$\text{value}(\text{IXI}) = \text{value}(\text{IIIIIXV}) = \text{value}(\text{X}) = 10$。

给你一个由罗马数码组成的数组 $s_1 \dots s_n$ 以及 $q$ 个形式为 $(\ell, r)$ 的独立询问。对于每个询问，计算子数组 $s_\ell \dots s_r$ 的值。

输入格式

第一行包含三个整数 $m$、$n$ 和 $q$（$1 \le m \le 10^5$，$1 \le n, q \le 3 \cdot 10^5$）：分别表示罗马数码的数量、给定数组的长度以及询问的数量。

接下来的 $m$ 行。其中第 $i$ 行包含两个整数 $p_i$ 和 $v_i$（$1 \le p_i \le m$，$1 \le v_i \le 10^9$），紧接着是一个由大小写英文字母组成的字符串 $d_i$（$1 \le |d_i| \le 7$）。它们分别表示第 $i$ 个罗马数码的优先级、数值和字符串表示。所有的 $d_i$ 都是互不相同的。

下一行包含 $n$ 个空格分隔的罗马数码表示 $s_1 \dots s_n$。

接下来的 $q$ 行，每行包含两个整数 $\ell$ 和 $r$（$1 \le \ell \le r \le n$）。

输出格式

对于每个询问，输出一行，包含一个整数：数字 $s_\ell \dots s_r$ 的值。

样例

输入样例 1

3 5 3
1 1 I
2 5 V
3 10 X
I X I V X
1 2
1 3
3 5

输出样例 1

9
10
6

输入样例 2

3 6 1
1 6 six
1 16 sixteen
1 60 sixty
six sixty six sixteen six sixteen
1 6

输出样例 2

110