终于到了这一天！你揭开了你的新发明——自动找零机（Auto-Coin-o-Matic）的面纱！你满怀喜悦与焦虑地看着人们将卡插入机器，输入他们想要的金额，并以最少的硬币数量获得准确的找零。

但这真的是最少的硬币数量吗？它是这样被编程的，但如果你有 bug 怎么办？没关系，你在观察。你决定随机抽取一些交易，并仔细检查机器给出的结果是否确实是可能的最少硬币数量。但是，糟糕，机器的某些类型的硬币快用完了！它还能正常工作吗？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2000, 1 \le m \le 10^5$)。

下一行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^5$)，表示最初可用的硬币面值。保证所有面值都是唯一的。

接下来的 $m$ 行，每行包含一个字符 $c$ ($c \in \{Q, X\}$) 和一个整数 $v$ ($1 \le v \le 10^5$)，其中 $c$ 是事件类型，$v$ 是事件的值。

• 如果 $c$ 是字符 $Q$，这是一个查询，输出应该是找零 $v$ 所需的最少硬币数量。保证至少有一个查询。 如果无法使用当前可用的面值准确凑出 $v$，则输出 $-1$。
• 如果 $c$ 是字符 $X$，这意味着机器的 $v$ 面值硬币已用尽。此后的所有查询都不能再使用该面值。保证每个 $X$ 事件对应的面值 $v$ 都是机器当前库存中有的。

输出格式

输出 $k$ 行，其中 $k$ 是查询事件（$c = Q$）的数量。在第 $i$ 行，输出第 $i$ 个查询所需的最少硬币数量，如果无法凑出，则输出 $-1$。

样例

样例输入 1

4 7
1 2 5 10
Q 23
X 1
Q 23
X 5
Q 23
X 10
Q 22

样例输出 1

4
6
-1
11