← 返回题目列表

AtCoder · past18_l

L. 重写

中文机器翻译题面 查看原题

问题陈述

黑板上写着一个整数。

高桥将执行以下程序: N 操作如下所述。 对于 i = 1, 2, \ldots, N, i- 第一个操作由一对字符串表示 s_i 和一个整数 p_i,其含义如下:

  • If s_i is NEGATE,将黑板上的整数替换为 -1 乘以该整数(忽略该值 p_i).
  • If s_i is CHMIN,如果黑板上的整数大于 p_i,替换为 p_i.
  • If s_i is CHMAX,如果黑板上的整数小于 p_i,替换为 p_i.

你被给予 Q 查询。 i = 1, 2, \ldots, Q, i第查询如下。

  • 如果在上述过程之前最初写在黑板上的整数是 q_i,找出经过程序后最后写在黑板上的整数。

打印每个问题的答案 Q 查询。

约束

  • N, Q, p_i,和 q_i 是整数。
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • -10^9 \leq p_i, q_i \leq 10^9
  • s_i is NEGATE, CHMIN,或 CHMAX.

输入

输入由标准输入按以下格式给出:

N Q
s_1 p_1
s_2 p_2
\vdots
s_N p_N
q_1
q_2
\vdots
q_Q

输出

打印 Q 行。 如下图所示,对于 i = 1, 2, \ldots, Q, i- 第行应包含答案 X_i 到 i第一个查询。

X_1
X_2
\vdots
X_Q

示例输入 1

4 5
CHMAX 3
NEGATE 5
CHMAX -11
NEGATE -12
2
7
15
9
-6

示例输出 1

3
7
11
9
3

对于第一个查询,即如果 在问题陈述中的程序之前,首先将 2 写在黑板上,操作步骤如下:

  • 在 1-st运算,黑板上的整数 2 小于 3,所以将其替换为 3.
  • 在 2-nd运算,与黑板上的整数相乘 3 by -1,将其替换为 -3.
  • 在 3-rd运算,黑板上的整数 -3 不小于 -11,所以什么也不做。
  • 在 4第运算,与黑板上的整数相乘 -3 by -1,将其替换为 3.

因此,在这种情况下,程序结束后最后写在黑板上的整数是 3,这是问题的答案 1-st 查询。


示例输入 2

15 10
CHMAX -14
CHMIN 12
CHMIN 6
NEGATE 10
CHMAX -8
NEGATE -2
NEGATE -20
NEGATE 14
NEGATE 15
NEGATE 5
NEGATE 12
CHMIN 13
CHMIN 20
CHMIN 16
NEGATE -3
-2
-7
6
-18
-20
-18
14
18
-13
-4

示例输出 2

-2
-7
6
-13
-13
-13
6
6
-13
-4