Radish Database Query

The Radish Database supports \(k\) fields (\(1 \le k \le 100\)), where each field has an integer as its name and stores an integer value. Initially the database is empty.

You are given \(n\) operations (\(1 \le n \le 1000\)). There are two kinds of operations:

• Insertion: Insert a record into the database. A record may provide values for a subset of the \(k\) fields. The format is: 1 m f_1 v_1 f_2 v_2 ... f_m v_m, where m is the number of fields provided in this record and for each \(i\), \(f_i\) is the field number and \(v_i\) is its value.
• Query: Query the database to count how many records satisfy given conditions. The format is: 2 m f_1 v_1 f_2 v_2 ... f_m v_m. A record satisfies the query if for every provided condition \((f_i, v_i)\) the record contains field \(f_i\) and its value equals \(v_i\). If a record does not have a field, it does not satisfy the condition.

Each operation is given in a separate line. For every query operation, output the count of records meeting the conditions on a separate line.

inputFormat

The first line contains two integers \(k\) and \(n\) denoting the number of fields and the number of operations.

Each of the following \(n\) lines represents an operation:

• If the operation is an insertion, the line begins with 1, followed by an integer \(m\) (the number of fields provided), then \(m\) pairs of integers \(f\) and \(v\) (the field number and its value).
• If the operation is a query, the line begins with 2, followed by an integer \(m\) (the number of conditions), then \(m\) pairs of integers \(f\) and \(v\) (the field number and the required value).

It is guaranteed that \(1 \le k \le 100\), \(1 \le n \le 1000\), and the field numbers used are within \([1, k]\).

outputFormat

For each query operation (operation type 2), output a single line containing the number of records that satisfy the query conditions.

sample

3 5
1 2 1 100 2 200
2 1 1 100
1 1 2 200
2 2 1 100 2 200
2 1 3 300

1
1
0