背景

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

题目描述

给出长度为 $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$ 次询问的答案。

10 6 8
5 1 2 1 7 2 1 3 6 3
1 5
2 7
3 6
4 5
7 10
5 9
1 3 1 3
2 4 1 4
5 6 1 5
2 2 2 3
4 6 3 3
2 5 2 6
1 3 1 7
3 5 4 9

3
3
2
2
2
2
3
1

15 10 10
1 2 1 3 2 4 1 2 3 5 4 1 2 5 3
1 7
8 15
3 10
1 15
5 12
1 3
13 15
6 9
2 5
10 13
1 4 1 2
1 10 3 4
6 9 1 5
1 5 5 5
4 4 1 5
9 9 2 2
1 3 4 5
7 10 1 1
1 10 6 10
5 8 2 3

4
3
2
2
4
2
2
1
0
2

提示

【样例解释 #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$	^
$3$	$2\times10^5$	A
$4$	$5\times10^4$	无	$20$
$5$	$10^5$	^
$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$。