Description

Xiao K is a customs officer at a harbor. Many ships arrive at the harbor every day, and there are usually many passengers on board from different countries.

Xiao K is very interested in these ships that arrive at the harbor. He records every ship in chronological order. For the $i$-th arriving ship, he records its 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_i}$.

Xiao K has collected information about $n$ ships. Please help him compute, for each ship’s arrival time, how many distinct countries the passengers come from among all ships that arrived within the last $24$ hours ($24$ hours $= 86400$ seconds), up to and including that time.

Formally, you need to compute $n$ values. For the $i$-th output, consider all ships $p$ satisfying $t_i - 86400 < t_p \le t_i$. Among all $x_{p,j}$ in these ships, count how many distinct values there are.

Input Format

The first line contains a positive integer $n$, indicating that Xiao K recorded information about $n$ ships.

Each of the next $n$ lines describes one ship: the first two integers $t_i$ and $k_i$ denote the ship’s arrival time and the number of passengers on board, followed by $k_i$ integers $x_{i,j}$, which are the nationalities of the passengers.

It is guaranteed that the $t_i$ are nondecreasing, measured in seconds. Counting from when Xiao K first started working, the $i$-th ship arrives at second $t_i$.

It is guaranteed that $1 \le n \le 10^5$, $\sum k_i \le 3 \times 10^5$, $1 \le x_{i,j} \le 10^5$, $1 \le t_{i-1} \le t_i \le 10^9$.

Here, $\sum k_i$ denotes the sum of all $k_i$.

Output Format

Output $n$ lines. On the $i$-th line, output one integer: the required statistic after the $i$-th ship arrives.

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

3
4
4

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

3
3
3
4

Hint

Sample Explanation 1:

The first ship arrives at second $1$. The ships that arrived in the last $24$ hours are just the first ship, with $4$ passengers from countries $4, 1, 2, 2$, for a total of $3$ distinct countries.

The second ship arrives at second $2$. The ships that arrived in the last $24$ hours are the first and second ships, with $4 + 2 = 6$ passengers from countries $4, 1, 2, 2, 2, 3$, for a total of $4$ distinct countries.

The third ship arrives at second $10$. The ships that arrived in the last $24$ hours are the first, second, and third ships, with $4 + 2 + 1 = 7$ passengers from countries $4, 1, 2, 2, 2, 3, 3$, for a total of $4$ distinct countries.

Sample Explanation 2:

The first ship arrives at second $1$. The ships that arrived in the last $24$ hours are just the first ship, with $4$ passengers from countries $1, 2, 2, 3$, for a total of $3$ distinct countries.

The second ship arrives at second $3$. The ships that arrived in the last $24$ hours are the first and second ships, with $4 + 2 = 6$ passengers from countries $1, 2, 2, 3, 2, 3$, for a total of $3$ distinct countries.

The third ship arrives at second $86401$. The ships that arrived in the last $24$ hours are the second and third ships, with $2 + 2 = 4$ passengers from countries $2, 3, 3, 4$, for a total of $3$ distinct countries.

The fourth ship arrives at second $86402$. The ships that arrived in the last $24$ hours are the second, third, and fourth ships, with $2 + 2 + 1 = 5$ passengers from countries $2, 3, 3, 4, 5$, for a total of $4$ distinct countries.

Constraints

• For $10\%$ of the test points, $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 points, $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 points, $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 points, $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 points, $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$.

Translated by ChatGPT 5