P14136 【MX-X22-T7】「TPOI-4G」终焉

一切都结束了，纵使一切还未开始。

给出长度为 $n$ 的正整数序列 $a_1,\ldots,a_n$ 和 $m$ 个区间 $[L_1,R_1],\ldots,[L_m,R_m]$（满足 $1 \le L_i \le R_i \le n$）。 有 $q$ 次询问，每次询问给出 $l,r,l',r'$，请你求出： $$\max\limits_{i=l}^r\max\limits_{k=l'}^{r'}\sum\limits_{j=L_i}^{R_i}[a_j=k]$$

第一行，三个正整数 $n,m,q$。 第二行，$n$ 个正整数 $a_1, \ldots, a_n$。 接下来 $m$ 行，第 $i$ 行两个正整数 $L_i,R_i$。 接下来 $q$ 行，每行四个正整数 $l, r, l', r'$，表示一次询问。

$q$ 行，第 $i$ 行一个非负整数，表示第 $i$ 次询问的答案。

**【样例解释 #1】** 对于第一个询问， - 当 $k=1$ 时，$\sum\limits_{j=L_1}^{R_1}[a_j=1]=2,\sum\limits_{j=L_2}^{R_2}[a_j=1]=3,\sum\limits_{j=L_3}^{R_3}[a_j=1]=1$； - 当 $k=2$ 时，$\sum\limits_{j=L_1}^{R_1}[a_j=2]=1,\sum\limits_{j=L_2}^{R_2}[a_j=2]=2,\sum\limits_{j=L_3}^{R_3}[a_j=2]=2$； - 当 $k=3$ 时，$\sum\limits_{j=L_1}^{R_1}[a_j=3]=0,\sum\limits_{j=L_2}^{R_2}[a_j=3]=0,\sum\limits_{j=L_3}^{R_3}[a_j=3]=0$。 其中的最大值为 $3$。 **【数据范围】** **本题采用捆绑测试。** |子任务编号|$n,m,q\le$|特殊性质|分值 | |:-----:|:--------:|:--:|:--:| |$1$ |$50$ |无 |$10$| |$2$ |$5000$ |^ |$10$| |$3$ |$2\times10^5$|A |$10$| |$4$ |$5\times10^4$|无 |$20$| |$5$ |$10^5$ |^ |$20$| |$6$ |$2\times10^5$|^ |$30$| - 特殊性质 A：序列 $a$ 中至多有 $100$ 种元素。 对于所有数据，保证 $1\le n,m,q\le 2\times 10^5$，$1\le a_i\le n$，$1\le L_i\le R_i\le n$，$1\le l\le r\le m$，$1\le l'\le r'\le n$。