가짜 뉴스 전파

Pak Dengklek은 방금 소셜 미디어 사이트를 개발했습니다. 이 사이트를 사용하는 사용자는 $N$명이며, $0$부터 $N - 1$까지 번호가 매겨져 있습니다. 하루는 $S$시간입니다. 모든 사용자는 매일 동일한 이용 일정을 따릅니다. $0 \le i \le N - 1$인 각 $i$에 대해, 사용자 $i$는 매일 $T[i]$번 온라인 상태가 됩니다:

• $A[i][0]^{th}$ 시간의 시작부터 $B[i][0]^{th}$ 시간의 끝까지,
• $A[i][1]^{th}$ 시간의 시작부터 $B[i][1]^{th}$ 시간의 끝까지,
• ...
• 그리고 $A[i][T[i] - 1]^{th}$ 시간의 시작부터 $B[i][T[i] - 1]^{th}$ 시간의 끝까지.

사이트의 모든 사용자는 언제든지 온라인 상태인 다른 모든 사용자에게 뉴스를 공유하고 싶어 합니다. 안타깝게도 첫째 날이 시작될 때 $N$명의 사용자 중 한 명이 가짜 뉴스를 가지고 있으며, 이를 퍼뜨릴 것입니다. 따라서 가짜 뉴스를 가진 사용자와 만나는 모든 사용자도 첫째 날이 끝날 때 가짜 뉴스를 가지게 됩니다. 두 사용자가 동시에 온라인 상태인 시간이 적어도 한 시간 있다면 두 사용자가 만났다고 합니다.

이 가짜 뉴스는 둘째 날에도 전파됩니다. 따라서 첫째 날이 끝날 때 가짜 뉴스를 가진 사용자와 만나는 모든 사용자도 둘째 날이 끝날 때 가짜 뉴스를 가지게 됩니다. 이 과정은 이후의 날들에도 계속됩니다.

각각 정수 $P$로 나타낼 수 있는 $Q$개의 시나리오가 있습니다. 각 시나리오에서 첫째 날이 시작될 때 가짜 뉴스를 가진 사용자는 사용자 $P$입니다. 서로 다른 시나리오에서는 가짜 뉴스가 서로 다르게 전파될 수 있습니다. 따라서 각 시나리오에 대해 Pak Dengklek은 $N^{th}$ 날이 끝날 때 가짜 뉴스를 가진 사용자의 수를 알고 싶어 합니다. 여기서 $N$은 사용자의 수입니다.

구현 세부사항

다음 프로시저를 구현해야 합니다:

void init(int N, int S, int[] T, int[][] A, int[][] B)

• $N$: 배열 $T$, $A$, $B$의 원소 수입니다.
• $S$: 하루의 시간 수입니다.
• $T$: 길이가 $N$인 배열로, 각 사용자가 매일 온라인 상태가 되는 횟수를 나타냅니다.
• $A, B$: 길이가 $N$인 배열입니다. $A[i]$와 $B[i]$는 길이가 $T[i]$인 배열로, 사용자 $i$가 매일 언제 온라인 상태가 되는지를 나타냅니다.
• 이 프로시저는 count_users가 호출되기 전에 정확히 한 번 호출됩니다.

int count_users(int P)

• $P$: 첫째 날이 시작될 때 가짜 뉴스를 가진 사용자의 인덱스입니다.
• 이 프로시저는 $N^{th}$ 날이 끝날 때 가짜 뉴스를 가진 사용자의 수를 반환해야 합니다. 여기서 $N$은 사용자의 수입니다.
• 이 프로시저는 정확히 $Q$번 호출됩니다.

예제

다음 호출 순서를 살펴봅시다:

init(5, 10, [2, 1, 1, 1, 1],
     [[2, 7], [1], [1], [9], [5]], [[4, 9], [3], [1], [10], [6]])

count_users(0)

이는 첫째 날이 시작될 때 사용자 $0$이 가짜 뉴스를 가지고 있음을 의미합니다. 사용자 $0$은 사용자 $1$과 만나고(두 번째 시간부터 세 번째 시간까지), 사용자 $3$과도 만납니다(아홉 번째 시간에). 따라서 첫째 날이 끝날 때 두 사용자가 가짜 뉴스를 가지게 됩니다. 사용자 $1$은 사용자 $2$와도 만납니다(첫 번째 시간에). 따라서 둘째 날이 끝날 때 사용자 $2$도 가짜 뉴스를 가지게 됩니다. 셋째 날, 넷째 날, 다섯째 날에는 가짜 뉴스가 더 이상 전파되지 않으므로, 다섯째 날이 끝날 때 $4$명의 사용자가 가짜 뉴스를 가지게 됩니다. 따라서 이 프로시저는 $4$를 반환해야 합니다.

count_users(4)

이는 첫째 날이 시작될 때 사용자 $4$가 가짜 뉴스를 가지고 있음을 의미합니다. 사용자 $4$는 다른 사용자와 만나지 않으므로, 다른 사용자는 가짜 뉴스를 가지지 않게 됩니다. 따라서 이 프로시저는 $1$을 반환해야 합니다.

제약 조건

• $1 \le N \le 200\;000$
• $1 \le S \le 10^9$
• $1 \le Q \le 100\;000$
• $1 \le T[i] \le S$ (각 $0 \le i \le N - 1$에 대해)
• $T$의 모든 원소의 합은 $200\;000$을 초과하지 않습니다.
• $1 \le A[i][j] \le B[i][j] \le S$ (각 $0 \le i \le N - 1$ 및 $0 \le j \le T[i] - 1$에 대해)
• $B[i][j - 1] \lt A[i][j]$ (각 $0 \le i \le N - 1$ 및 $1 \le j \le T[i] - 1$에 대해)
• $0 \le P \le N - 1$
• 모든 시나리오에서 $P$의 값은 서로 다릅니다.

서브태스크

1. (15점) $N, S, Q \le 50$이고 $T$의 모든 원소의 합은 $50$을 초과하지 않습니다.
2. (17점) $N, Q \le 50$이고 $T$의 모든 원소의 합은 $50$을 초과하지 않습니다.
3. (21점) $N, Q \le 300$이고 $T$의 모든 원소의 합은 $300$을 초과하지 않습니다.
4. (26점) $N, Q \le 2000$이고 $T$의 모든 원소의 합은 $2000$을 초과하지 않습니다.
5. (21점) 추가 제약 조건이 없습니다.

샘플 그레이더는 다음 형식으로 입력을 읽습니다:

• $1$번째 줄: $N \; S \; Q$
• $2 + i$번째 줄 ($0 \le i \le N - 1$): $T[i] \; A[i][0] \; B[i][0] \; \ldots \; A[i][T[i] - 1] \; B[i][T[i] - 1]$
• $2 + N + k$번째 줄 ($0 \le k \le Q - 1$): 시나리오 $k$에 대한 $P$

샘플 그레이더는 다음 형식으로 답을 출력합니다:

• $1 + k$번째 줄 ($0 \le k \le Q - 1$): 시나리오 $k$에 대한 count_users의 반환 값