题目描述

小可有一个特别的数字爱好，她收集了一个长度为 $n$ 的整数数组 $A$，数组中的每个数字都在 $-m$ 到 $m$ 之间。现在，小可想要玩一个有趣的游戏，并邀请你来参加。

在游戏中，小可会给出 $q$ 个查询，每个查询都会给出两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示数组 $A$ 中的一个子数组范围。对于每个查询，你需要帮助小可找出在这个子数组范围内的所有数字中，哪一个数字出现的次数最多，并输出这个数字及其出现的次数。

输入格式

第一行包含三个整数 $n$，$m$ 和 $q$，分别表示数组 $A$ 的长度、数字的范围和查询的数量。

第二行包含 $n$ 个整数，表示数组 $A$ 的元素。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$，表示一个查询的范围。

输出格式

对于每个查询，输出一行，包含 $2$ 个整数，表示出现次数最多的数字，以及出现的次数。如果有多个数字出现次数相同且最多，则输出值最小的数。

样例

5 3 2
1 2 2 3 1
1 3
3 5

2 2
1 1

5 5 3
1 2 -2 -2 5
1 3
2 5
1 5

-2 1
-2 2
-2 2

提示

样例1解释

在第一个查询中，子数组 $A[1,3]=[1,2,2]$，数字 $2$ 出现了 $2$ 次，次数最多，次数为 $2$。因此输出 $2$ $2$。

在第二个查询中，子数组 $A[3,5]=[2,3,1]$，数字 $2$ 、$3$ 和 $1$ 都出现了 $1$ 次，次数相同且最多，因此输出 $1$ $1$。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 50$
• $1 \leq q \leq 10^5$
• $-m \leq a_i \leq m$