Auto-Coin-o-Matic

It is finally here! The day you unveil your new invention, the Auto-Coin-o-Matic, has arrived. People insert their card, type in the amount they want, and get exact change back with the fewest number of coins. You watch with glee and anxiety.

Was it actually the fewest number of coins? That is how the machine was programmed, but what if there is a bug? It is okay, you are watching. You decide to randomly pick some transactions and check whether the machine gave out the fewest coins possible. But the machine is running out of certain types of coins. Will it still work correctly?

The input starts with two integers $n$ and $m$ ($1 \le n \le 2000$, $1 \le m \le 10^5$).

The next line contains $n$ integers, $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 10^5$), the denominations of coins available initially. All denominations are unique.

The next $m$ lines each contain a character $c$ ($c \in \{Q, X\}$) and an integer $v$ ($1 \le v \le 10^5$), where $c$ is the type of event and $v$ is its value.

• If $c$ is Q, this is a query. Output the minimum number of coins needed to give out exactly $v$. If it is not possible to make $v$ exactly with the available denominations, output $-1$.
• If $c$ is X, the machine is out of coins of denomination $v$. All later queries cannot use that denomination. Each X event refers to a denomination $v$ that the machine currently has in stock.

Output $k$ lines, where $k$ is the number of query events. On the $i$th line, output the fewest number of coins needed for the $i$th query, or $-1$ if it is impossible.