Problems for Later

Cheongrin joined DOJ to improve her problem-solving skills and started solving problems recommended by her friends.

DOJ has a tag system for classifying problems. Each problem has zero or more tags among $K$ possible tags.

Cheongrin represents a tag list as a bit string of length $K$. For a bit string $S$, if the $i$-th character from the left, $S_i$, is $1$, then the tag list contains tag $i$; otherwise it does not contain tag $i$. If a problem has tag list $S$, then it has exactly the tags represented by $S$.

Cheongrin does not solve recommended problems immediately. Instead, she stores them in a list of problems to solve later. Initially, this list is empty. Process the following $Q$ queries.

• 1 S x: Add $x$ problems with tag list $S$ to the list.
• 2 S x: Remove $x$ problems with tag list $S$ from the list. It is guaranteed that at least $x$ such problems are currently in the list.
• 3 S: Print the number of problems currently in the list that contain every tag contained in tag list $S$.

For a type $3$ query, a counted problem only needs to contain all tags contained in $S$. That is, for every $i$ with $S_i=1$, the problem must also have tag $i$; tags with $S_i=0$ do not matter.

The input is given in the following format.

$K\ Q$ $query_1$ $query_2$ $\vdots$ $query_Q$

Each $query_j$ ($1 \leq j \leq Q$) is given in one of the following formats: 1 S x, 2 S x, or 3 S.

For each query of the form 3 S, print the number of problems satisfying the condition on a separate line.

• $1 \leq K \leq 24$.
• $1 \leq Q \leq 100\ 000$.
• In every query, $S$ is a bit string of length $K$.
• In queries of the form 1 S x and 2 S x, $1 \leq x \leq 10^9$.
• Whenever a query 2 S x is given, at least $x$ problems with tag list $S$ are currently in the list.