P1076潮声四界定音（tonic）

【题目背景】

群钥归位、星门开启后，tfbz 在通往内陆的旧档案库中发现了一卷由潮声写成的长谱。谱面以四道界标圈出每次可以截取的范围，Ehundategh 需要从层层回声中找出其中最清晰的一声主音。

【题目描述】

长谱上依次记录着 $n$ 个整数 $x_1,x_2,\ldots,x_n$，每个整数表示一段潮声的音高。

对于一个非空连续片段，将其中的所有音高从小到大排列。若片段长度为 $z$，排列后的第 $\lfloor z/2\rfloor+1$ 个音高称为这个片段的定音。特别地，当片段长度为偶数时，定音是中间两个音高中较大的一个。

Ehundategh 一共需要处理 $q$ 组四界记录。每组记录给出四个位置 $a,b,c,d$，满足 $a\leq b<c\leq d$。Ehundategh 可以在 $[a,b]$ 中选择片段的左端点 $l$，并在 $[c,d]$ 中选择片段的右端点 $r$。

形式化题意：给定长度为 $n$ 的整数序列 $\{x\}$ 与 $q$ 组整数 $a,b,c,d$，对于每组询问，求

其中 $\operatorname{med}$ 表示一个非空序列的中位数，当序列长度为偶数时取中间两个数中较大的一个。

【输入格式】

从文件 $\textbf{\textit{tonic.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示长谱长度与四界记录的数量。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示长谱上的音高。

接下来 $q$ 行，每行包含四个正整数 $a,b,c,d$，表示一组四界记录。

【输出格式】

输出到文件 $\textbf{\textit{tonic.out}}$ 中。

对于每组四界记录输出一行一个整数，表示能够得到的最大定音。

【样例 1 输入】

10 225 331 5 2 4 341 2 4 552 2 4 461 1 3 576 286 1 5 2 4 391 2 4 6102 3 5 6

【样例 1 输出】

1424344554

【说明/提示】

【样例 1 解释】

在第一组测试数据的第一组记录中，选择 $l=1,r=4$ 时，片段中的音高从小到大为 $1,2,4,5$，定音为 $4$。其余合法选择都不能得到更大的定音。

【样例 2】

见选手目录下的 $\textbf{\textit{tonic/tonic2.in}}$ 和 $\textbf{\textit{tonic/tonic2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{tonic/tonic3.in}}$ 和 $\textbf{\textit{tonic/tonic3.ans}}$。

该组样例符合测试点 $4\sim 7$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{tonic/tonic4.in}}$ 和 $\textbf{\textit{tonic/tonic4.ans}}$。

该组样例符合测试点 $8\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{tonic/tonic5.in}}$ 和 $\textbf{\textit{tonic/tonic5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{tonic/tonic6.in}}$ 和 $\textbf{\textit{tonic/tonic6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$2\leq n\leq 10^5$，$1\leq q\leq 10^5$，$\lvert x_i\rvert\leq 10^9$，$1\leq a\leq b<c\leq d\leq n$。对于同一个测试点，保证 $\sum n,\sum q\leq 10^5$。

令 $v$ 表示一组测试数据的序列中不同整数的数量。

特殊性质：每组四界记录均满足 $a=b$ 且 $c=d$。