题目描述

整数列 $ A\ =\ (a_1,\ a_2,\ \dots,\ a_N),\ T\ =\ (t_1,\ t_2,\ \dots,\ t_N),\ X\ =\ (x_1,\ x_2,\ \dots,\ x_Q) $ が与えられます。
$N$ 個の関数 $f_1(x),\ f_2(x),\ \dots,\ 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,\ \dots,\ Q$ のそれぞれについて、 $f_N(\ \dots\ f_2(f_1(x_i))\ \dots\ )$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $t_1$ $a_2$ $t_2$ $\vdots$ $a_N$ $t_N$ $Q$ $x_1$ $x_2$ $\cdots$ $x_Q$

输出格式

$Q$ 行にかけて出力せよ。 $i$ 行目には、 $f_N(\ \dots\ f_2(f_1(x_i))\ \dots\ )$ を出力せよ。

题目大意

题目描述

给出整数数列 $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$。

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

0
0
5
10
10

提示

制約

• 入力は全て整数
• $1\ <\ =\ N\ <\ = 2\ \times\ 10^5$
• $1\ <\ =\ Q\ <\ = 2\ \times\ 10^5$
• $|a_i|\ <\ =\ 10^9$
• $1\ <\ = t_i\ <\ = 3$
• $|x_i|\ <\ =\ 10^9$

Sample Explanation 1

$ f_1(x)\ =\ \max(x,\ -10),\ f_2(x)\ =\ x\ +\ 10,\ f_3(x)\ =\ \min(x,\ 10) $ です。 したがって、 - $f_3(f_2(f_1(-15)))\ =\ 0$ - $f_3(f_2(f_1(-10)))\ =\ 0$ - $f_3(f_2(f_1(-5)))\ =\ 5$ - $f_3(f_2(f_1(0)))\ =\ 10$ - $f_3(f_2(f_1(5)))\ =\ 10$ となります。