题目背景

扶苏和 10circle 老师正在拼机游玩最新最热歌曲 Latent Kindom（LK）！

LK 这首歌共有 $n$ 个难度的谱面，第 $i$ 个难度的谱面有 $l_i$ 个音符，分别是 $a_{i, 1}, a_{i, 2}, \dots a_{i, l_i}$，构成了一个序列。

扶苏想知道，如果她开难度为 $i$ 的谱面，10circle 老师开难度为 $j$ 的谱面，那么两个谱面的音符序列合并起来的中位数是多少。

题目描述

给定 $n$ 个序列 $a_1, a_2, \dots a_n$。你要回答 $q$ 次询问，每次询问会给出 $i, j$，你要求出序列 $a_i$ 和 $a_j$ 拼接后的中位数是多少。

拼接两个序列 $x, y$ 指的是把 $y$ 序列中的数依次写在 $x$ 序列后面。如果得到的序列长度为 $t$，中位数指的是序列中第 $\left\lceil\frac t 2 \right\rceil$ 小的数字。其中 $\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数。

需要注意的是，本题的询问是独立的。也就是说，虽然你要回答假设 $a_i$ 和 $a_j$ 拼接后的中位数，但是不会真的进行对数列拼接的操作。

输入格式

本题单个测试点内有多组测试数据。输入的第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是两个整数 $n,q$（$2 \leq n, q \leq 10^6$），表示序列的个数和询问的次数。
接下来 $n$ 行，每行表示一个序列。第 $i$ 行首先有一个整数 $l_i$（$1 \leq l_i \leq 10^6$），表示序列 $a_i$ 的长度。接下来 $l_i$ 个整数，表示序列 $a_i$。保证序列里的数都是不大于 $10^{18}$ 的正整数。
接下来 $q$ 行，每行两个整数 $i,j$（$1 \leq i,j \leq n$，$i \neq j$）表示一组询问。

数据保证单个测试点内的 $n,q,l_i$ 之和均不超过 $10^6$。

输出格式

对每组数据的每组询问，输出一行一个整数表示答案。

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

2
4
4

提示

提示

请注意大量的数据读入输出对程序效率造成的影响，使用合适的读入输出方式，不要频繁刷新输出缓冲区，避免超时。