AT_past18_l 書き換え

黒板に $ 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 $ $ 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 $

### Sample Explanation 1 $ 1 $ 個目の質問の場合、すなわち、高橋君が問題文中の手順を始める前の時点で黒板に書かれている整数が $ 2 $ である場合の手順は下記の通りです。 - $ 1 $ 番目の操作では、黒板に書かれた整数 $ 2 $ は $ 3 $ より小さいので、黒板に書かれた整数を $ 3 $ に書き換えます。 - $ 2 $ 番目の操作では、黒板に書かれた整数 $ 3 $ を、それを $ -1 $ 倍した $ -3 $ に書き換えます。 - $ 3 $ 番目の操作では、黒板に書かれた整数 $ -3 $ は $ -11 $ より小さくはないので、何もしません。 - $ 4 $ 番目の操作では、黒板に書かれた整数 $ -3 $ を、それを $ -1 $ 倍した $ 3 $ に書き換えます。 よって、この場合の高橋君が上記の手順を終えた後の時点で黒板に書かれている整数は $ 3 $ であり、 $ 1 $ 番目の質問に対する答えは $ 3 $ です。 ### Constraints - $ 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` のいずれか