CF1200F.Graph Traveler

Gildong is experimenting with an interesting machine Graph Traveler. In Graph Traveler, there is a directed graph consisting of $n$ vertices numbered from $1$ to $n$. The $i$-th vertex has $m_i$ outgoing edges that are labeled as $e_i[0]$, $e_i[1]$, $\ldots$, $e_i[m_i-1]$, each representing the destination vertex of the edge. The graph can have multiple edges and self-loops. The $i$-th vertex also has an integer $k_i$ written on itself.

A travel on this graph works as follows.

1. Gildong chooses a vertex to start from, and an integer to start with. Set the variable $c$ to this integer.
2. After arriving at the vertex $i$, or when Gildong begins the travel at some vertex $i$, add $k_i$ to $c$.
3. The next vertex is $e_i[x]$ where $x$ is an integer $0 \le x \le m_i-1$ satisfying $x \equiv c \pmod {m_i}$. Go to the next vertex and go back to step 2.

It's obvious that a travel never ends, since the 2nd and the 3rd step will be repeated endlessly.

For example, assume that Gildong starts at vertex $1$ with $c = 5$, and $m_1 = 2$, $e_1[0] = 1$, $e_1[1] = 2$, $k_1 = -3$. Right after he starts at vertex $1$, $c$ becomes $2$. Since the only integer $x$ ($0 \le x \le 1$) where $x \equiv c \pmod {m_i}$ is $0$, Gildong goes to vertex $e_1[0] = 1$. After arriving at vertex $1$ again, $c$ becomes $-1$. The only integer $x$ satisfying the conditions is $1$, so he goes to vertex $e_1[1] = 2$, and so on.

Since Gildong is quite inquisitive, he's going to ask you $q$ queries. He wants to know how many distinct vertices will be visited infinitely many times, if he starts the travel from a certain vertex with a certain value of $c$. Note that you should not count the vertices that will be visited only finite times.

吉尔东正在试验一台有趣的机器——图旅行器（Graph Traveler）。在图旅行器中，存在一个由 $n$ 个顶点构成的有向图，顶点编号从 $1$ 到 $n$。第 $i$ 个顶点有 $m_i$ 条出边，分别标记为 $e_i[0],\, e_i[1],\, \ldots,\, e_i[m_i-1]$，每条边指向其目标顶点。该图允许存在重边和自环。第 $i$ 个顶点上还写有一个整数 $k_i$。

在该图上的旅行过程如下：

1. 吉尔东选择一个起始顶点和一个起始整数。将变量 $c$ 设为该整数。
2. 每当到达顶点 $i$（包括旅行初始时位于顶点 $i$），将 $k_i$ 加到 $c$ 上。
3. 下一个顶点为 $e_i[x]$，其中 $x$ 是满足 $0 \le x \le m_i-1$ 且 $x \equiv c \pmod {m_i}$ 的整数。前往下一个顶点，并返回步骤 2。

显然，该旅行永远不会终止，因为步骤 2 和步骤 3 将无限重复。

例如，假设吉尔东从顶点 $1$ 出发，初始 $c = 5$，且 $m_1 = 2$，$e_1[0] = 1$，$e_1[1] = 2$，$k_1 = -3$。他刚在顶点 $1$ 开始旅行时，$c$ 变为 $2$。由于在 $0 \le x \le 1$ 范围内唯一满足 $x \equiv c \pmod {m_i}$ 的整数是 $x = 0$，吉尔东前往顶点 $e_1[0] = 1$。再次到达顶点 $1$ 后，$c$ 变为 $-1$。此时唯一满足条件的 $x$ 是 $1$，因此他前往顶点 $e_1[1] = 2$，依此类推。

由于吉尔东十分好奇，他将向你提出 $q$ 个询问。他想知道：若从某个特定顶点出发、并以某个特定的 $c$ 值开始旅行，则最终会被无限次访问的不同顶点的个数是多少？注意：你不应计入那些仅被有限次访问的顶点。

The first line of the input contains an integer $n$ ($1 \le n \le 1000$), the number of vertices in the graph.

The second line contains $n$ integers. The $i$-th integer is $k_i$ ($-10^9 \le k_i \le 10^9$), the integer written on the $i$-th vertex.

Next $2 \cdot n$ lines describe the edges of each vertex. The $(2 \cdot i + 1)$-st line contains an integer $m_i$ ($1 \le m_i \le 10$), the number of outgoing edges of the $i$-th vertex. The $(2 \cdot i + 2)$-nd line contains $m_i$ integers $e_i[0]$, $e_i[1]$, $\ldots$, $e_i[m_i-1]$, each having an integer value between $1$ and $n$, inclusive.

Next line contains an integer $q$ ($1 \le q \le 10^5$), the number of queries Gildong wants to ask.

Next $q$ lines contains two integers $x$ and $y$ ($1 \le x \le n$, $-10^9 \le y \le 10^9$) each, which mean that the start vertex is $x$ and the starting value of $c$ is $y$.

输入的第一行包含一个整数 $n$（$1 \le n \le 1000$），表示图中顶点的数量。

第二行包含 $n$ 个整数。其中第 $i$ 个整数为 $k_i$（$-10^9 \le k_i \le 10^9$），表示写在第 $i$ 个顶点上的整数。

接下来的 $2 \cdot n$ 行描述每个顶点的边。第 $(2 \cdot i + 1)$ 行包含一个整数 $m_i$（$1 \le m_i \le 10$），表示第 $i$ 个顶点的出边数量；第 $(2 \cdot i + 2)$ 行包含 $m_i$ 个整数 $e_i[0],\, e_i[1],\, \ldots,\, e_i[m_i-1]$，每个值均在 $1$ 到 $n$（含）之间。

下一行包含一个整数 $q$（$1 \le q \le 10^5$），表示 Gildong 想要提出的查询次数。

接下来的 $q$ 行每行包含两个整数 $x$ 和 $y$（$1 \le x \le n$，$-10^9 \le y \le 10^9$），表示起始顶点为 $x$，且变量 $c$ 的初始值为 $y$。

For each query, print the number of distinct vertices that will be visited infinitely many times, if Gildong starts at vertex $x$ with starting integer $y$.

对于每个查询，请输出：如果吉隆从顶点 $x$ 出发，且初始整数为 $y$，则会被无限次访问的不同顶点的数量。

The first example can be shown like the following image:

Three integers are marked on $i$-th vertex: $i$, $k_i$, and $m_i$ respectively. The outgoing edges are labeled with an integer representing the edge number of $i$-th vertex.

The travel for each query works as follows. It is described as a sequence of phrases, each in the format "vertex ($c$ after $k_i$ added)".

• $1(0) \to 2(0) \to 2(0) \to \ldots$
• $2(0) \to 2(0) \to \ldots$
• $3(-1) \to 1(-1) \to 3(-1) \to \ldots$
• $4(-2) \to 2(-2) \to 2(-2) \to \ldots$
• $1(1) \to 3(1) \to 4(1) \to 1(1) \to \ldots$
• $1(5) \to 3(5) \to 1(5) \to \ldots$

The second example is same as the first example, except that the vertices have non-zero values. Therefore the answers to the queries also differ from the first example.

The queries for the second example works as follows:

• $1(4) \to 2(-1) \to 2(-6) \to \ldots$
• $2(-5) \to 2(-10) \to \ldots$
• $3(-4) \to 1(0) \to 2(-5) \to 2(-10) \to \ldots$
• $4(-3) \to 1(1) \to 3(-2) \to 4(-3) \to \ldots$
• $1(5) \to 3(2) \to 1(6) \to 2(1) \to 2(-4) \to \ldots$
• $1(9) \to 3(6) \to 2(1) \to 2(-4) \to \ldots$

第一个示例可如下图所示：

第 $i$ 个顶点上标记有三个整数：$i$、$k_i$ 和 $m_i$。从该顶点出发的边用整数标注，表示该顶点的第几条出边。

每次查询的遍历过程如下所述，其形式为一系列短语，每个短语格式为“顶点（在加上 $k_i$ 后的 $c$ 值）”。

• $1(0) \to 2(0) \to 2(0) \to \ldots$
• $2(0) \to 2(0) \to \ldots$
• $3(-1) \to 1(-1) \to 3(-1) \to \ldots$
• $4(-2) \to 2(-2) \to 2(-2) \to \ldots$
• $1(1) \to 3(1) \to 4(1) \to 1(1) \to \ldots$
• $1(5) \to 3(5) \to 1(5) \to \ldots$

第二个示例与第一个示例相同，仅顶点上的值非零。因此，各查询的答案也与第一个示例不同。

第二个示例的查询过程如下：

• $1(4) \to 2(-1) \to 2(-6) \to \ldots$
• $2(-5) \to 2(-10) \to \ldots$
• $3(-4) \to 1(0) \to 2(-5) \to 2(-10) \to \ldots$
• $4(-3) \to 1(1) \to 3(-2) \to 4(-3) \to \ldots$
• $1(5) \to 3(2) \to 1(6) \to 2(1) \to 2(-4) \to \ldots$
• $1(9) \to 3(6) \to 2(1) \to 2(-4) \to \ldots$