K. Kwords Find Kth Element
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Hello, guys. I am Kwords. I prepared a problem for the contest invited by Hsueh-.

Due to I was very boring, I generate $$$n$$$ arrays, labeled from $$$1$$$ to $$$n$$$. And then I will give $$$q$$$ queries.

In each queries:

  • First, I will give a interger $$$m$$$, and then $$$m$$$ different intergers.
  • You need to merge the arrays pointed to by these $$$m$$$ labels which I given.
  • Then, I will give a interger $$$k$$$.
  • You need to answer me, what is the $$$k$$$-$$$th$$$ smallest number in the combined array.

It is attention that, each query is independent. It means that the array merging operation of a single query will not affect other queries.

Input

The first line contains a single interger $$$n(1 \leq n \leq 10^5)$$$, denoting the number of arrays.

The next $$$n$$$ lines, for each line:

  • First give a single integer $$$m_i(1 \leq m_i \leq 10^5)$$$, denoting the size of the $$$i$$$-$$$th$$$ array.
  • Followed by $$$m_i$$$ integers $$$a_{i, j}(1 \leq a_{i, j} \leq 10^9)$$$, denoting the $$$j$$$-$$$th$$$ number in the $$$i$$$-$$$th$$$ array.

The $$$n + 1$$$ line contains a single integer $$$q(1 \leq q \leq 10^5)$$$, denoting the number of queriyes.

The next $$$q$$$ liens, for each line:

  • First give a single integer $$$l_i(1 \leq l_i \leq 10^5)$$$, denoting the size of the $$$i$$$-$$$th$$$ index query.
  • Followed by $$$l_i$$$ distinct integers $$$b_{i, j}(1 \leq b_{i, j} \leq n)$$$, denoting the $$$j$$$-$$$th$$$ index in the $$$i$$$-$$$th$$$ query.
  • Last will given a single interge $$$k_i(1 \leq k_i \leq \sum\limits_{j = 1}^{l_i} array[b_{j}].size())$$$, denoting you need to find $$$k$$$-$$$th$$$ smallest element in the combined array.

It is guaranteed that $$$\sum\limits_{i = 1}^{n} m_i \leq 10^5$$$ and $$$\sum\limits_{i = 1}^{q} l_i \leq 10^5$$$.

Output

For each query, you should print the $$$k$$$-$$$th$$$ smallest element in the combined array in a single line.

Example
Input
5
1 1
2 2 3
3 5 10 6
4 4 58 2 1
5 1000000000 9 8 4 5
5
1 2 2
2 2 3 3
3 3 4 5 11
4 5 4 3 2 1
5 1 2 5 4 3 7
Output
3
5
58
1
4