AT_past18_l 書き換え

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.

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 $

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 Explanation 1 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. ### 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`, or `CHMAX`.