题目描述

给出整数数列 $A=(a_1,a_2,...,a_n)$，$T=(t_1,t_2,...,t_n)$，$X=(x_1,x_2,...,x_q)$。

定义 $n$ 个函数 $f_1(x),f_2(x),...,f_n(x)$：

$$f_i(x)=\begin{cases} x+a_i& t_i=1\\ \max(x,a_i)& t_i=2\\ \min(x,a_i)& t_i=3\\ \end{cases} $$

对于 $i=1,2,...,q$，求出 $f_n(...f_2(f_1(x_i))...)$ 的值。

输入格式

第一行一个整数 $n$，为函数的个数。

接下来 $n$ 行每行两个整数 $a_i,t_i$，含义如题面所示。

下一行有一个整数 $q$，为需要求值的点数。

接下来一行 $q$ 个整数，第 $i$ 个数为 $x_i$。

输出格式

输出$q$ 行，第 $i$ 行为 $f_n(...f_2(f_1(x_i))...)$ 的值。

数据范围

对于 $100\%$ 的数据所有输入的值均为整数，$1 \leqslant n,q \leqslant 2 \times 10^5$，$1 \leqslant t_i \leqslant 3$，$|a_i|,|x_i| \leqslant 10^9$。