Concatenated Sequence Median

You are given n sequences \(a_1, a_2, \dots, a_n\). You have to answer q queries. In each query, two indices \(i\) and \(j\) are given and you are asked to determine the median of the sequence formed by concatenating \(a_i\) followed by \(a_j\).

The concatenation of two sequences \(x\) and \(y\) means writing the numbers of sequence \(y\) right after those of sequence \(x\). If the resulting sequence has length \(t\), the median is defined as the \(\left\lceil \frac{t}{2} \right\rceil\)-th smallest element. Here, \(\left\lceil x \right\rceil\) denotes the smallest integer not less than \(x\).

Note: Each query is independent, meaning that although you calculate the median of the concatenated sequences, you are not actually merging the sequences permanently.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space.

The following \(2 \times n\) lines describe the \(n\) sequences. For each \(i\) from 1 to \(n\):

• The first line contains an integer \(m_i\) representing the length of sequence \(a_i\).
• The second line contains \(m_i\) space-separated integers representing the elements of \(a_i\).

The next \(q\) lines each contain two integers \(i\) and \(j\) (1-indexed), representing a query to compute the median of the concatenation of \(a_i\) and \(a_j\).

outputFormat

For each query, output the median of the concatenated sequence on a new line. The median is the \(\left\lceil \frac{t}{2} \right\rceil\)-th smallest number of the concatenated sequence (where \(t\) is the total length of the concatenated sequence).

sample

3 3
3
1 3 5
2
2 4
4
7 8 9 10
1 2
2 3
1 3

3
7
7