分数: 500 点
问题陈述
给定的是整数序列 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 ).
约束
- 输入中的所有值都是整数。
- 1 ≤ N ≤ 2 \times 10^5
- 1 ≤ Q ≤ 2 \times 10^5
- |a_i| ≤ 10^9
- 1 ≤ t_i ≤ 3
- |x_i| ≤ 10^9
输入
输入由标准输入按以下格式给出:
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 ).
示例输入 1
3 -10 2 10 1 10 3 5 -15 -10 -5 0 5
示例输出 1
0 0 5 10 10
我们有 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