P10237 [yLCPC2024] E. Latent Kindom

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?

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.

**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$.

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

#### 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