Distinctive_Features (OOI qualification)
Time limit: 3 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: line sweep, range queries, offline queries, binary indexed tree

# Distinctive Features

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 3 seconds       |
| Memory limit: | 512 megabytes   |

You are developing a system to assist consultants in smartphone stores.

All smartphones in the store are arranged in a row and numbered with integers from 1 to $n$ in the order they are placed.

Each smartphone has certain distinctive features, such as durability or a large battery. There are a total of $m$ different distinctive features, and they are numbered with integers from 1 to $m$.

The most common question that consultants have to answer is: how does this smartphone differ from those next to it? We formalize this question as follows:

Given a segment of smartphones numbered from $l_i$ to $r_i$ inclusive, and the number of a certain smartphone $p_i$ in this segment ($l_i \le p_i \le r_i$), determine how many distinctive features are present in the given smartphone $p_i$ but not in any other smartphone in the segment $[l_i, r_i]$.

To make the consultants' work easier, you have been tasked with developing a system capable of efficiently answering such queries.

## Input

The first line contains three integers $n$, $m$, and $g$ ($1 \le n, m \le 500\,000$, $0 \le g \le 9$) — the number of smartphones in the store, the number of different distinctive features, and the group number for this test.

Each of the following $n$ lines describes the distinctive features of the next smartphone in the following format:

At the beginning of the line is an integer $k_i$ ($0 \le k_i \le m$) — the number of distinctive features of the $i$-th smartphone. Then in the same line are $k_i$ integers $1 \le a_{i,1} < \dots < a_{i,k_i} \le m$ — the distinctive features of the $i$-th smartphone in increasing order.

The next line contains an integer $q$ ($1 \le q \le 500\,000$) — the number of queries.

The following $q$ lines describe the queries. In the $i$-th line, there are three integers $l_i$, $r_i$, and $p_i$ ($1 \le l_i \le p_i \le r_i \le n$) — the parameters of the $i$-th query.

Let $s$ denote the total number of distinctive features across all smartphones ($s = \sum_{i=1}^{n} k_i$). It is guaranteed that $n, m \le s \le 500\,000$.

## Output

Output $q$ integers — the number of distinctive features for each query.

## Example

| standard input | standard output |
|----------------|-----------------|
| 6 4 0          | 0               |
| 2 1 3          | 0               |
| 0              | 3               |
| 2 1 4          | 1               |
| 3 2 3 4        | 1               |
| 2 1 2          |                 |
| 2 2 3          |                 |
| 5              |                 |
| 1 3 2          |                 |
| 4 4 4          |                 |
| 3 5 4          |                 |
| 1 3 1          |                 |
| 4 6 5          |                 |

## Note

Consider the example.

In the first query, the second smartphone has no distinctive features, so the answer to the query is zero.

In the second query, the segment consists of a single element, so all distinctive features of the fourth smartphone apply.

In the third query, the distinctive features of the third smartphone are $[1, 4]$, the fourth smartphone has $[2, 3, 4]$, and the fifth smartphone has $[1, 2]$. Among all the distinctive features of the fourth smartphone, only feature 3 is unique to it, so the answer to the query is 1.

## Scoring

The tests for this problem consist of nine groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Points | Additional Constraints | Required Groups | Comment |
|-------|--------|--------------------------|-----------------|-----------------------|
| 0     | 0      | –                        | –               | Samples.              |
| 1     | 10     | $n, m, q \le 500$         | 0               | -                     |
| 2     | 7      | $q \le 5000, s \le 10\,000$   | 0               | -                     |
| 3     | 13     | $q, s \le 100\,000, m \le 500$ | 0               | -                     |
| 4     | 19     | –                        | –               | $p_i = l_i$           |
| 5     | 7      | –                        | –               | $l_i = 1$             |
| 6     | 10     | –                        | –               | $l_i \le l_{i+1}, r_i \le r_{i+1}$ |
| 7     | 12     | $q, s \le 100\,000$        | 0, 2, 3         | -                     |
| 8     | 7      | $q, s \le 200\,000$        | 0, 2, 3, 7      | -                     |
| 9     | 15     | –                        | 0 – 8           | Offline-testing.      |

Starter code:

Grader code:

Setup script:

Evaluation script: