| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.8 초 | 8 MB | 9 | 0 | 0 | 0.000% |
After the events that took place in New York, the N worlds from the Marvel Universe are at war. The world i (1 ≤ i ≤ N) is represented, in this final war, by an army consisting of Ki soldiers (possibly zero). Each soldier has a single super power represented by a positive integer (between 1 and P). The powers of all the soldiers in an army are different.
It has been observed that, in direct battle, two soldiers annihilate each other if and only if they have the same power. For example, if an army consisting of soldiers with powers {1, 3, 5} battles an army {2, 3, 6}, the following soldiers remain alive at the end of the battle: {1, 2, 5, 6}.
The N worlds are arranged sequentially. The first world has index 1 and the last world has index N.
Thanos is pretty sure that he can win the war and destroy the universe, but he also wants to have fun while doing it. He has prepared Q questions for you. For each question you are given two indexes x and y and you have to find the number of soldiers that would survive a battle between the armies with indexes x, x + 1, ..., y.
The first line of the input contains two numbers N and Q.
The next N lines contain the descriptions of the armies. Line i+1 (where 1 ≤ i ≤ N) contains a number Ki (number of soldiers) followed by Ki numbers (power number of each soldier).
The next Q lines each contain two numbers x and y separated by a space.
The output must contain Q lines. Each line must contain a single number, the answer to the corresponding question.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | N ≤ 10,000, P ≤ 500 and Q ≤ 10,000 |
| 2 | 30 | P ≤ 5,000 and Q ≤ 30,000 |
| 3 | 40 | none |
4 3 2 1 2 3 1 3 97 2 1 341 5 4 2 981 341 97 1 3 2 4 1 4
5 4 4