Problem Description

Chipmunks really like to sneak and eat the production team’s big carrots, so Huālìshǔ Tech University is studying a new type of database called the Carrot Database.

More specifically, it supports $k$ fields ($1 \leq k \leq 100$). Each field name is an integer, and the value stored in it is also an integer.

Now you need to support the following operations:

• Insert a record into the database. It may contain only a subset of the $k$ fields. The exact operation format is described in “Input Format”.

• Query how many records in the database satisfy a given condition.

You will perform a total of $n$ operations ($1 \leq n \leq 1000$). For each query operation, output the result.

Input Format

The first line contains two integers $n, k$, with meanings as described above.

Each of the following lines represents one operation, as follows:

• $1\ p\ x_1\ \ y_1,...,x_p\ y_p$: indicates an insertion operation. There are $p$ fields. The name of the $i$-th field is $x_i$, and its value is $y_i$. Here we guarantee that $1 \leq x_i \leq k$, $1 \leq y_i \leq 1000$, and both $x_i$ and $y_i$ are integers.

• $2\ x\ y_{min}\ y_{max}$: indicates a query operation. It asks how many records satisfy that the value of field $x$ is within $[y_{min}, y_{max}]$.

Output Format

For each query operation, output one line with one integer, representing the number of records that satisfy the condition.

4 5
1 2 1 2 2 4
2 2 1 5
1 2 3 5 4 6
2 4 7 8

1
0

Hint

Translated by ChatGPT 5