问题陈述
黑板上写着一个整数。
高桥将执行以下程序: 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