/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
黒板に 1 個のある整数が書かれています。
高橋君は次に述べる N 個の操作からなる手順を行います。 i = 1, 2, \ldots, N について、i 番目に行う操作は文字列 s_i と 整数 p_i の組で表され、その意味は下記の通りです。
- s_i が
NEGATEのとき、黒板に書かれた整数を、それを -1 倍したものに書き換える（ p_i の値は無視する）。 - s_i が
CHMINのとき、もし黒板に書かれた整数が p_i より大きいならば、黒板に書かれた整数を p_i に書き換える。 - s_i が
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 は
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 行目には i 番目の質問に対する答え X_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
1 個目の質問の場合、すなわち、高橋君が問題文中の手順を始める前の時点で黒板に書かれている整数が 2 である場合の手順は下記の通りです。
- 1 番目の操作では、黒板に書かれた整数 2 は 3 より小さいので、黒板に書かれた整数を 3 に書き換えます。
- 2 番目の操作では、黒板に書かれた整数 3 を、それを -1 倍した -3 に書き換えます。
- 3 番目の操作では、黒板に書かれた整数 -3 は -11 より小さくはないので、何もしません。
- 4 番目の操作では、黒板に書かれた整数 -3 を、それを -1 倍した 3 に書き換えます。
よって、この場合の高橋君が上記の手順を終えた後の時点で黒板に書かれている整数は 3 であり、1 番目の質問に対する答えは 3 です。
入力例 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
Problem Statement
An integer is written on a blackboard.
Takahashi will perform a procedure consisting of N operations described below. For i = 1, 2, \ldots, N, the i-th operation is represented by a pair of a string s_i and an integer p_i, whose meanings are as follows:
- If s_i is
NEGATE, replace the integer on the blackboard with -1 times that integer (ignoring the value p_i). - If s_i is
CHMIN, if the integer on the blackboard is greater than p_i, replace it with p_i. - If s_i is
CHMAX, if the integer on the blackboard is less than p_i, replace it with p_i.
You are given Q queries. For i = 1, 2, \ldots, Q, the i-th query is as follows.
- If the integer initially written on the blackboard before the procedure above is q_i, find the integer finally written on the blackboard after the procedure.
Print the answer for each of the Q queries.
Constraints
- N, Q, p_i, and q_i are integers.
- 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, orCHMAX.
Input
The input is given from Standard Input in the following format:
N Q s_1 p_1 s_2 p_2 \vdots s_N p_N q_1 q_2 \vdots q_Q
Output
Print Q lines. As shown below, for i = 1, 2, \ldots, Q, the i-th line should contain the answer X_i to the i-th query.
X_1 X_2 \vdots X_Q
Sample Input 1
4 5 CHMAX 3 NEGATE 5 CHMAX -11 NEGATE -12 2 7 15 9 -6
Sample Output 1
3 7 11 9 3
For the first query, that is, if 2 is initially written on the blackboard before the procedure in the problem statement, the operations proceed as follows:
- In the 1-st operation, the integer on the blackboard 2 is less than 3, so replace it with 3.
- In the 2-nd operation, multiply the integer on the blackboard 3 by -1, replacing it with -3.
- In the 3-rd operation, the integer on the blackboard -3 is no less than -11, so do nothing.
- In the 4-th operation, multiply the integer on the blackboard -3 by -1, replacing it with 3.
Thus, in this case, the integer finally written on the blackboard after the procedure is 3, which is the answer to the 1-st query.
Sample Input 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
Sample Output 2
-2 -7 6 -13 -13 -13 6 6 -13 -4