题目描述

小 Q 被一个数列迷住了。他发现这个数列可以分为连续的 $N$ 段，其中第 $i$ 段是连续 $a_i$ 个 $p_i$。小 Q 在想有没有快速求数列第 $K$ 项的方法呢？于是他开始不断尝试计算数列第 $k_i$ 项 的值，但计算量太大，小 Q 想用程序来实现自动计算，你来帮帮他吧。

输入格式

第一行有一个整数 $N$，表示数列分为 $N$ 个重复段。
接下来有 N 行，每行有两个整数 $a_i$，$p_i$, 表示第 i 段重复了 $a_i$ 个 $p_i$ 。
第 N+2 行有一个整数 $M$，表示小 Q 有 $M$ 个查询。
接下来有 M 个整数 $k_i$，表示小 Q 需要计算数列中第 $k_i$ 项的值。

数据范围

60%的数据 1 <= N <=1000 , 1 <= $a_i$ <=1000 , 1 <= $p_i$ <= 1000 ,1<=M<=1000 ,1 <= $k_i$ <= ${10}^6$ 。
100%的数据 1 <= N <=${10}^5$ , 1 <= $a_i$ <= ${10}^6$, 1 <= $p_i$ <= ${10}^6$ ,1 <= M <= 10000, 1 <= $k_i$ <= ${10}^9$。

输出格式

输出数据有 M 个，每个数依次对应了小 Q 一次查询的结果。

样例

2
5 1
3 2
3
1 4 8

1 1 2

样例解释
数列有 2 个重复段如下： 1 1 1 1 1 2 2 2
小 Q 有 3 个查询，分别查询第1项、第4项和第8项。
查询结果为：
数列中第1项的值为 1
第4项的值为 1
第8项的值为 2。