Auto-Coin-o-Matic

드디어 새 발명품 Auto-Coin-o-Matic을 공개하는 날이다. 사람들은 카드를 넣고 원하는 금액을 입력한 뒤, 가장 적은 개수의 동전으로 정확한 잔돈을 받는다. 당신은 기쁘면서도 불안한 마음으로 그 모습을 지켜본다.

기계가 정말로 가장 적은 개수의 동전을 냈는지 확인하려고, 거래를 몇 개 무작위로 골라 검증하기로 한다. 그런데 기계에서 일부 종류의 동전이 떨어지고 있다. 그래도 기계가 올바르게 동작할까?

첫 줄에 정수 $n$과 $m$ ($1 \le n \le 2000$, $1 \le m \le 10^5$)이 주어진다.

다음 줄에는 처음에 보유한 동전의 액면가 $d_1, d_2, \ldots, 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$줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 잔돈을 주는 데 필요한 동전의 최소 개수를 출력한다. 불가능하면 $-1$을 출력한다.