题目描述

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

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

输入格式

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

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

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

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

2
1

2
2
2

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