B. Digit occurrence Sum
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ distinct non-negative currently available integers $$$a_1, a_2, ..., a_n$$$. Define the function $$$count(x)$$$ as the number of times the digit $$$x$$$ appears in all currently available integers. For any integer $$$k$$$, $$$f(k)$$$ is defined as the sum of $$$count(x)$$$ for each digit $$$x$$$ in $$$k$$$.

For example, let's consider the currently available integers: $$$70, 123, 311, 125$$$. In this case, $$$count(0) = 1$$$, $$$count(1) = 4$$$, and so on. For $$$f(311)$$$, we have $$$count(3) + count(1) + count(1) = 2 + 4 + 4 = 10.$$$

You will be given $$$q$$$ queries, each of which can be one of the following three types:

1. $$$+\;k$$$: Add integer $$$k$$$ to the currently available integers if it's not already present. If $$$k$$$ is already in the list, remove it.

2. $$$-\;k$$$: Delete the $$$k$$$-th largest integer from the currently available integers. If there are fewer than $$$k$$$ integers available, skip this operation.

3. $$$?\;k$$$: Print $$$f(k)$$$ if $$$k$$$ is currently available among the integers. If $$$k$$$ is not available, print $$$-1$$$.

Input

The first line consists of two integers $$$n, q$$$.

Second line consists of $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$.

Next $$$q$$$ lines each consist of $$$-\;k$$$, $$$+\;k$$$ or $$$?\;k$$$.

$$$1 \leq n, q \leq 3 \times 10^5$$$

$$$1 \leq a_i \leq 2 \times 10^9$$$

Output

For each "$$$?\;k$$$" In the query, Print $$$f(k)$$$ if $$$k$$$ is currently available. Otherwise print $$$-1$$$.

Example
Input
4 6
70 123 311 125
? 123
- 2
? 123
+ 234
- 3
? 123
Output
8
6
-1