Problem Background

NOIP2016 Junior Group T3

Problem Description

Xiao K is a customs officer at a harbor, where many ships arrive daily, carrying passengers from various countries.

Xiao K is very interested in these ships arriving at the harbor. He records the details of each ship that arrives; for the \(i\)-th ship, he notes the arrival time \(t_i\) (in seconds), the number of passengers \(k_i\), and the nationality of each passenger \(x_{i,1}, x_{i,2}, \dots, x_{i,k}\).

Xiao K has compiled information on \(n\) ships and would like you to help calculate the number of different countries represented by the passengers who have arrived in the past 24 hours (24 hours = 86400 seconds) up to the arrival time of each ship.

Formally, you need to compute \(n\) pieces of information. For the \(i\)-th piece of output, you need to count the ships \(p\) that satisfy \(t_i - 86400 < t_p \leq t_i\), and determine how many distinct numbers there are among all \(x_{p,j}\).

Input Format

The first line contains a positive integer \(n\), representing the number of ships Xiao K has recorded.

The next \(n\) lines describe the information for each ship: the first two integers \(t_i\) and \(k_i\) represent the arrival time of the ship and the number of passengers, respectively. The following \(k_i\) integers \(x_{i,j}\) represent the nationalities of the passengers on the ship.

The input guarantees that \(t_i\) is strictly increasing, measured in seconds from when Xiao K started work, indicating the ship arrived at the harbor at the \(t_i\)-th second.

Constraints: \(1 \leq n \leq 10^5\), \(\sum{k_i} \leq 3 \times 10^5\), \(1 \leq x_{i,j} \leq 10^5\), \(1 \leq t_{i-1} \leq t_i \leq 10^9\).

Here, \(\sum{k_i}\) denotes the sum of all \(k_i\).

Output Format

Output \(n\) lines, where the \(i\)-th line contains an integer representing the number of distinct countries from the passengers who arrived in the past 24 hours up to the \(i\)-th ship's arrival.

Sample Input and Output

Sample Input #1

3
1 4 4 1 2 2
2 2 2 3
10 1 3

Sample Output #1

3
4
4

Sample Input #2

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

Sample Output #2

3
3
3
4

Notes

Explanation of Sample 1

• The first ship arrives at the 1st second, and within the last 24 hours, only the first ship has arrived. There are 4 passengers from countries 4, 1, 2, 2, representing 3 different countries.
• The second ship arrives at the 2nd second, and within the last 24 hours, the first and second ships have arrived. There are 6 passengers from countries 4, 1, 2, 2, 2, 3, representing 4 different countries.
• The third ship arrives at the 10th second, and within the last 24 hours, the first, second, and third ships have arrived. There are 7 passengers from countries 4, 1, 2, 2, 2, 3, 3, representing 4 different countries.

Explanation of Sample 2

• The first ship arrives at the 1st second, and within the last 24 hours, only the first ship has arrived. There are 4 passengers from countries 1, 2, 2, 3, representing 3 different countries.
• The second ship arrives at the 3rd second, and within the last 24 hours, the first and second ships have arrived. There are 6 passengers from countries 1, 2, 2, 3, 2, 3, representing 3 different countries.
• The third ship arrives at the 86401st second, and within the last 24 hours, the second and third ships have arrived. There are 4 passengers from countries 2, 3, 3, 4, representing 3 different countries.
• The fourth ship arrives at the 86402nd second, and within the last 24 hours, the second, third, and fourth ships have arrived. There are 5 passengers from countries 2, 3, 3, 4, 5, representing 4 different countries.

Data Range

• For 10% of the test cases, \(n = 1\), \(\sum k_i \leq 10\), \(1 \leq x_{i,j} \leq 10\), \(1 \leq t_i \leq 10\).
• For 20% of the test cases, \(1 \leq n \leq 10\), \(\sum k_i \leq 100\), \(1 \leq x_{i,j} \leq 100\), \(1 \leq t_i \leq 32767\).
• For 40% of the test cases, \(1 \leq n \leq 100\), \(\sum k_i \leq 100\), \(1 \leq x_{i,j} \leq 100\), \(1 \leq t_i \leq 86400\).
• For 70% of the test cases, \(1 \leq n \leq 1000\), \(\sum k_i \leq 3000\), \(1 \leq x_{i,j} \leq 1000\), \(1 \leq t_i \leq 10^9\).
• For 100% of the test cases, \(1 \leq n \leq 10^5\), \(\sum k_i \leq 3 \times 10^5\), \(1 \leq x_{i,j} \leq 10^5\), \(1 \leq t_i \leq 10^9\).

见题面 Input 部分

见题面 Output 部分