题目描述
整数列 $ 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 個の関数 f1(x), f2(x), …, fN(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 のそれぞれについて、 fN( … f2(f1(xi)) … ) を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
N a1 t1 a2 t2 ⋮ aN tN Q x1 x2 ⋯ xQ
输出格式
Q 行にかけて出力せよ。 i 行目には、 fN( … f2(f1(xi)) … ) を出力せよ。
题目大意
题目描述
给出整数数列 A=(a1,a2,...,an),T=(t1,t2,...,tn),X=(x1,x2,...,xq)。
定义 n 个函数 f1(x),f2(x),...,fn(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,求出 fn(...f2(f1(xi))...) 的值。
输入格式
第一行一个整数 n,为函数的个数。
接下来 n 行每行两个整数 ai,ti,含义如题面所示。
下一行有一个整数 q,为需要求值的点数。
接下来一行 q 个整数,第 i 个数为 xi。
输出格式
输出q 行,第 i 行为 fn(...f2(f1(xi))...) 的值。
数据范围
对于 100% 的数据所有输入的值均为整数,1⩽n,q⩽2×105,1⩽ti⩽3,∣ai∣,∣xi∣⩽109。
3
-10 2
10 1
10 3
5
-15 -10 -5 0 5
0
0
5
10
10
提示
制約
- 入力は全て整数
- 1 < = N < = 2 × 105
- 1 < = Q < = 2 × 105
- ∣ai∣ < = 109
- 1 < = ti < = 3
- ∣xi∣ < = 109
Sample Explanation 1
$ f_1(x)\ =\ \max(x,\ -10),\ f_2(x)\ =\ x\ +\ 10,\ f_3(x)\ =\ \min(x,\ 10) $ です。 したがって、 - f3(f2(f1(−15))) = 0 - f3(f2(f1(−10))) = 0 - f3(f2(f1(−5))) = 5 - f3(f2(f1(0))) = 10 - f3(f2(f1(5))) = 10 となります。