题目描述

我们想把一个数字变好，会经过n ($n<=10^5$)个操作，每个早做由整数 $a_i,t_i$ 表示。每次操作，若 $t_i=1$ ，则把 x 变为 $x+a_i$ ；若 $t_i=2$ ,着把 x 变为 $max(x,a_i)$,若 $t_i=3$ ,着把 x 变为 $min(x,a_i)$ ($a_i<10^9$)

给定你 q 个数，请输出他们变好后的结果

输入

第一行输出一个正整数 n ,

接下来输入 n 行， 分别表示 $a_i,t_i$

然后输入 1 个整数 q

接下来一行有q 个整数，表示每组询问

输出

输出q 行，每行一个整数

样例

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

0
0
5
10
10

限制

1s, 512MB 每组测试数据