题目描述

哈基米发明了一种无损压缩算法。

对于待压缩数列 $A=(A_1, A_2, \cdots, A_n)$，按照 $i$ 从小到大依次处理 $A_i$，其中 $w$ 的初始值为 $0$。

• 若 $i\neq 1$ 且 $A_i \neq A_{i-1}$，压缩结果增加一项 $[A_{i-1}, w]$，并将 $w$ 置 $1$。
• 若 $i=1$ 或 $A_i=A_{i-1}$，$w$ 增加 $1$。

例如，$A=(1, 1, 1, 3, 3, 2)$ 可以被压缩为 $[1, 3], [3, 2], [2, 1]$。

现在，压缩结果中共有 $n$ 项，请你计算原数列中第 $x$ 项（即 $A_x$）的值。

输入格式

第一行为一个正整数 $n$。

接下来 $n$ 行，每行两个正整数 $v_i, l_i$，表示压缩结果中的一项。

接下来一行一个正整数 $T$，表示询问的个数。

接下来 $T$ 行，每行一个正整数，表示一个 $x$。

输出格式

输出 $T$ 行，每行一个整数，表示 $A_x$ 的值。

3
1 3
3 2
2 1
6
1
2
3
4
5
6

1
1
1
3
3
2

提示

对于 $30\%$ 的测试数据，$l_i = 1$。

对于 $100\%$ 的测试数据，$1 \le n \le 10^3$，$1 \le T \le 10^3$，$1 \le x\le \sum l_i \le 10^9$，$1 \le v_i, l_i \le 10^9$。