Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
130 - ZOJ Monthly, January 2014 - C
Chameleon

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Given n groups of integers(all the integers are distinct). You should answer Q queries in this problem.

Each query contains a pair of integers (i, j). For each query, you must perform below operations:

  1. List the i-th group and the j-th group in a line. These integers form an array ci.
  2. Sort ci in ascending order.
  3. Answer this question: how many i satisfy that GroupIDi-1 GroupIDi after sorting. Here GroupIDi equals to the group id which ci belongs to. That means the value of GroupID must be either i or j in this query.

Input

The input file contains multiple test cases.

Each case begin with an integer n which indicate the amount of group. The following n lines each describe a group of integers. The format of these lines is:

mi ai1 ai2 ai3 ... aimi (1 ≤ in, 1 ≤ aij ≤ 109)

We guarantee that m1 + m2 + m3 + ... + mn ≤ 105

There is a number Q(1 ≤ Q ≤ 105) after these groups of integers. This number is followed by Q lines, each contains two numbers (i, j)(1 ≤ i, jn and ij) which describe a query.

Process to the End Of File.

Output

Output an integer in a line for each query.

Sample Input

2
3 1 5 8
3 2 6 7
1
1 2

Sample Output

4

Hint

In the sample, we get c = {1, 5, 8, 2, 6, 7}, GruopID = {1, 1, 1, 2, 2, 2}.

After sorting, it becomes c = {1, 2, 5, 6, 7, 8}, GruopID = {1, 2, 1, 2, 2, 1}.


Author: CHEN, Weijie
Submit    Status