Background

Fusu and Teacher 10circle are playing the newest and hottest song Latent Kindom (LK) together on one setup.

The song LK has $n$ charts of different difficulties. The chart of difficulty $i$ has $l_i$ notes, which are $a_{i, 1}, a_{i, 2}, \dots a_{i, l_i}$, forming a sequence.

Fusu wants to know: if she plays the chart of difficulty $i$ and Teacher 10circle plays the chart of difficulty $j$, what is the median of the note sequence after merging the two sequences?

Background

Fusu and Teacher 10circle are playing the newest and hottest song Latent Kindom (LK) together on one setup.

The song LK has $n$ charts of different difficulties. The chart of difficulty $i$ has $l_i$ notes, which are $a_{i, 1}, a_{i, 2}, \dots a_{i, l_i}$, forming a sequence.

Fusu wants to know: if she plays the chart of difficulty $i$ and Teacher 10circle plays the chart of difficulty $j$, what is the median of the note sequence after merging the two sequences?

Problem Description

You are given $n$ sequences $a_1, a_2, \dots a_n$. You need to answer $q$ queries. Each query gives $i, j$, and you must find the median of the sequence obtained by concatenating $a_i$ and $a_j$.

Concatenating two sequences $x, y$ means writing the numbers of sequence $y$ one by one after sequence $x$. If the resulting sequence has length $t$, the median is defined as the $\left\lceil\frac t 2 \right\rceil$-th smallest number in the sequence. Here, $\left\lceil x \right\rceil$ denotes the smallest integer that is not less than $x$.

Note that the queries in this problem are independent. That is, although you are asked for the median after concatenating $a_i$ and $a_j$, you will not actually perform any concatenation operation on the sequences.

Input Format

This problem contains multiple testcases within a single test point. The first line of the input is a positive integer $T$, indicating the number of testcases. For each testcase:

The first line contains two integers $n, q$ ($2 \leq n, q \leq 10^6$), representing the number of sequences and the number of queries.
The next $n$ lines each describe a sequence. In the $i$-th line, the first integer is $l_i$ ($1 \leq l_i \leq 10^6$), the length of sequence $a_i$. Then follow $l_i$ integers, representing sequence $a_i$. It is guaranteed that all numbers in the sequences are positive integers not greater than $10^{18}$.
The next $q$ lines each contain two integers $i, j$ ($1 \leq i, j \leq n$, $i \neq j$), representing a query.

It is guaranteed that, within a single test point, the sums of $n$, $q$, and all $l_i$ do not exceed $10^6$.

Output Format

For each query of each testcase, output one line with one integer, representing the answer.

1
3 3
1 1
2 2 3
3 4 5 6
1 2
1 3
2 3

2
4
4

Hint

Hint

Please note that reading and writing a large amount of data can affect the program’s efficiency. Use appropriate input/output methods, do not flush the output buffer frequently, and avoid TLE.

Translated by ChatGPT 5