{"raw_statement":[{"iden":"background","content":"扶苏和 10circle 老师正在拼机游玩最新最热歌曲 Latent Kindom（LK）！\n\nLK 这首歌共有 $n$ 个难度的谱面，第 $i$ 个难度的谱面有 $l_i$ 个音符，分别是 $a_{i, 1}, a_{i, 2}, \\dots a_{i, l_i}$，构成了一个序列。\n\n扶苏想知道，如果她开难度为 $i$ 的谱面，10circle 老师开难度为 $j$ 的谱面，那么两个谱面的音符序列合并起来的中位数是多少。"},{"iden":"statement","content":"给定 $n$ 个序列 $a_1, a_2, \\dots a_n$。你要回答 $q$ 次询问，每次询问会给出 $i, j$，你要求出序列 $a_i$ 和 $a_j$ 拼接后的中位数是多少。\n\n拼接两个序列 $x, y$ 指的是把 $y$ 序列中的数依次写在 $x$ 序列后面。如果得到的序列长度为 $t$，中位数指的是序列中第 $\\left\\lceil\\frac t 2 \\right\\rceil$ 小的数字。其中 $\\left\\lceil x \\right\\rceil$ 表示不小于 $x$ 的最小整数。\n\n需要注意的是，本题的询问是独立的。也就是说，虽然你要回答假设 $a_i$ 和 $a_j$ 拼接后的中位数，但是不会真的进行对数列拼接的操作。"},{"iden":"input","content":"**本题单个测试点内有多组测试数据**。输入的第一行是一个正整数 $T$，表示数据组数。对每组数据：\n\n第一行是两个整数 $n,q$（$2 \\leq n, q \\leq 10^6$），表示序列的个数和询问的次数。  \n接下来 $n$ 行，每行表示一个序列。第 $i$ 行首先有一个整数 $l_i$（$1 \\leq l_i \\leq 10^6$），表示序列 $a_i$ 的长度。接下来 $l_i$ 个整数，表示序列 $a_i$。保证序列里的数都是不大于 $10^{18}$ 的正整数。  \n接下来 $q$ 行，每行两个整数 $i,j$（$1 \\leq i,j \\leq n$，$i \\neq j$）表示一组询问。\n\n数据保证单个测试点内的 $n,q,l_i$ 之和均不超过 $10^6$。"},{"iden":"output","content":"对每组数据的每组询问，输出一行一个整数表示答案。"},{"iden":"note","content":"#### 提示\n\n请注意大量的数据读入输出对程序效率造成的影响，使用合适的读入输出方式，不要频繁刷新输出缓冲区，避免超时。"}],"translated_statement":null,"sample_group":[["1\n3 3\n1 1\n2 2 3\n3 4 5 6\n1 2\n1 3\n2 3","2\n4\n4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}