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], …, 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 ≤ x ≤ m_i-1 satisfying x ≡ 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 ≤ x ≤ 1) where x ≡ 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.

Input

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

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

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

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

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

Output

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.

Examples

Input


4
0 0 0 0
2
2 3
1
2
3
2 4 1
4
3 1 2 1
6
1 0
2 0
3 -1
4 -2
1 1
1 5


Output


1
1
2
1
3
2


Input


4
4 -5 -3 -1
2
2 3
1
2
3
2 4 1
4
3 1 2 1
6
1 0
2 0
3 -1
4 -2
1 1
1 5


Output


1
1
1
3
1
1

Note

The first example can be shown like the following image:

<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) → 2(0) → 2(0) → … 
  * 2(0) → 2(0) → … 
  * 3(-1) → 1(-1) → 3(-1) → … 
  * 4(-2) → 2(-2) → 2(-2) → … 
  * 1(1) → 3(1) → 4(1) → 1(1) → … 
  * 1(5) → 3(5) → 1(5) → … 



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.

<image>

The queries for the second example works as follows:

  * 1(4) → 2(-1) → 2(-6) → … 
  * 2(-5) → 2(-10) → … 
  * 3(-4) → 1(0) → 2(-5) → 2(-10) → … 
  * 4(-3) → 1(1) → 3(-2) → 4(-3) → … 
  * 1(5) → 3(2) → 1(6) → 2(1) → 2(-4) → … 
  * 1(9) → 3(6) → 2(1) → 2(-4) → … 
import java.io.*;
import java.util.*;

public class F implements Runnable {
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int n = fs.nextInt();
		int[] vals = fs.nextIntArray(n);
		int[][] adj = new int[n][];
		int lcm = -1;
		for(int i = 0; i < n; i++) {
			int x = fs.nextInt();
			if(lcm == -1) lcm = x;
			else lcm = lcm(lcm, x);
			adj[i] = fs.nextIntArray(x);
			for(int j = 0; j < x; j++) adj[i][j]--;
		}
		
		int[][] vis = new int[n][lcm];
		int[][] size = new int[n][lcm];
		
		int LEN = 2*n*lcm+10;
		int[] stack2 = new int[LEN];
		int[] stack = new int[LEN];
		int[] queue = new int[LEN];
		int[] lastTime = new int[n];
		int curTime = 0;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < lcm; j++) {
				if(vis[i][j] != 0) continue;
				curTime++;
				int tail = 0;
				int tail2 = 0;
				int tail3 = 0;
				queue[tail++] = i;
				queue[tail++] = j;
				vis[i][j] = 1;
				for(int k = 0; k < tail; k += 2) {
					int u = queue[k], time = queue[k+1];
					stack[tail2++] = u; stack[tail2++] = time;
					
					
					int idx = time % adj[u].length;
					int v = adj[u][idx];
					int time2 = time+vals[v];
					time2 %= lcm;
					while(time2 < 0) time2 += lcm;
					
					if(vis[v][time2] == 0) {
						vis[v][time2] = 1;
						queue[tail++] = v; queue[tail++] = time2;
					}
					else if(vis[v][time2] == 1) {
						int sz = 0;
						while(tail2 > 0) {
							tail2 -= 2;
							int uu = stack[tail2], time3 = stack[tail2+1];
							
							if(lastTime[uu] != curTime) {
								sz++;
								lastTime[uu] = curTime;
							}
							
							vis[uu][time3] = 2;
							stack2[tail3++] = uu; stack2[tail3++] = time3;
							if(uu == v && time3 == time2) break;
						}
						while(tail3 > 0) {
							tail3 -= 2;
							int uu = stack2[tail3], time3 = stack2[tail3+1];
							size[uu][time3] = sz;
						}
					}
				}
				
				while(tail2 > 0) {
					tail2 -= 2;
					int u = stack[tail2], time = stack[tail2+1];

					int idx = time % adj[u].length;
					int v = adj[u][idx];
					int time2 = time+vals[v];
					time2 %= lcm;
					while(time2 < 0) time2 += lcm;

					vis[u][time] = 2;
					size[u][time] = size[v][time2];
				}
				
			}
		}
		
		int q = fs.nextInt();
		while(q-->0) {
			int x = fs.nextInt()-1;
			int y = fs.nextInt();
			y += vals[x];
			y %= lcm;
			while(y < 0) y += lcm;
			out.println(size[x][y]);
		}
		
		out.close();
	}
	
	int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
	
	int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a % b);
	}
	
	class Pair {
		int x, y;
		Pair(int a, int b) {
			x = a; y = b;
		}
		public String toString() {
			return String.format("(%d, %d)", x, y);
		}
	}
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}