题目描述

你的朋友 Klaudiusz 正准备进行一系列山地旅行。

山区中有 $n$ 个重要地点（山峰或山屋），编号为 $1,2,\ldots,n$，并由 $m$ 条双向步道连接。地点 $i$ 的景观吸引力为 $t_i$。

Klaudiusz 计划了 $q$ 次旅行。第 $i$ 次旅行从 $a_i$ 出发，到 $b_i$ 结束。

他不喜欢走回头路，因此旅行路线必须是一条简单路径：在同一次旅行中，任何地点都不能被访问超过一次。

一条路线的吸引力定义为该路线经过的所有地点（包括起点和终点）中最大的 $t_i$。

对于每次询问，请求出从 $a_i$ 到 $b_i$ 的所有简单路径中，能够得到的最大可能吸引力。

输入格式

第一行包含三个整数 $n,m,q$：

• $2\le n\le100000$；
• $1\le m\le200000$；
• $1\le q\le100000$。

第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$，其中：

$1\le t_i\le10^9$。

接下来 $m$ 行，每行包含两个整数 $u_i,v_i$，表示存在一条连接 $u_i$ 与 $v_i$ 的双向步道。

保证：

• $1\le u_i,v_i\le n$，$u_i\ne v_i$；
• 任意两个地点之间至多存在一条直接步道；
• 整张图连通。

接下来 $q$ 行，每行包含两个整数 $a_i,b_i$，表示一次旅行的起点和终点，且 $a_i\ne b_i$。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 次旅行能够达到的最大可能吸引力。

样例

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

10
9
5

样例说明

• 对于 $3\to1$，可走 $3\to4\to5\to1$，经过点的吸引力为 $10,5,4,9$，最大值为 $10$。
• 对于 $2\to5$，可走 $2\to1\to5$，得到最大值 $9$；直接走 $2\to5$ 只能得到 $7$。
• 对于 $4\to5$，唯一简单路径是直接边 $4\to5$，因此答案为 $5$。

子任务