Nikuniku 热爱长非递减子序列。她有一个 0-1 字符串 $s$，并希望使 $s$ 的最长非递减子序列尽可能长。

0-1 字符串仅由“0”和“1”两种字符组成，其中“0”被认为小于“1”。字符串的子序列是指从原字符串中删除若干（可以为零）字符后，不改变剩余字符的相对位置所形成的新字符串（例如，“010”是“0110”的子序列，而“001”不是）。

Nikuniku 决定对字符串进行一些修改。每次修改可以反转 $s$ 的任意子串（即令 $s[l, r] = s_r s_{r-1} \dots s_l$）。她想知道在最多进行 $k$ 次修改后，最长非递减子序列的长度是多少（简称为 $\text{revlis}(s, k)$），对于 $q$ 个不同的 $k$ 值分别求解。注意，$q$ 个查询是相互独立的。

由于字符串 $s$ 可能非常长，Nikuniku 决定以游程编码（run-length encoded）的形式给出它。一个游程编码字符串包含 $n$ 个部分，每个部分有 $p_i$ 个相同的字符 $c_i$。例如，字符串“001111”包含两个部分，$p_1$ 为 2，$c_1$ 为“0”，$p_2$ 为 4，$c_2$ 为“1”。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示字符串 $s$ 的部分数量。

接下来的 $n$ 行描述这些部分。每行包含一个字符 $c_i$ ($c_i \in \{'0', '1'\}$) 和一个整数 $p_i$ ($1 \le p_i \le 10^9$)，中间用空格隔开。保证对于 $1 \le i \le n - 1$，有 $c_i \neq c_{i+1}$。

下一行包含一个整数 $q$ ($1 \le q \le 2 \cdot 10^5$)，表示查询的数量。接下来的 $q$ 行，每行包含一个整数 $k_i$ ($0 \le k_i \le n$)。

输出格式

对于每个查询，输出一行，包含一个整数，即 $\text{revlis}(s, k_i)$ 的值。

样例

输入 1

4
0 1
1 2
0 3
1 4
2
0
1

输出 1

8
10

输入 2

5
1 2
0 5
1 2
0 5
1 2
3
5
0
5

输出 2

16
12
16

输入 3

7
0 1
1 3
0 7
1 6
0 6
1 6
0 6
2
1
5

输出 3

26
35