407824: GYM102897 K Kwords Find Kth Element

K. Kwords Find Kth Elementtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputHello, 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.

ExampleInput

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