Đất nước Alpha bao gồm ~n~ thành phố. Hiện tại, các thành phố được đánh số từ ~1~ đến ~n~, ở thành phố thứ ~i~ đang có dân số là ~a_i~.

Sắp tới, để cải cách lại đất nước, nhà vua quyết định sẽ hợp nhất một số thành phố lại với nhau. Các đại thần đã dâng lên nhà vua ~m~ đề xuất, trong đề xuất thứ ~i~, hai thành phố ~x_i~ và ~y_i~ sẽ được hợp nhất lại với nhau.

Sau khi nhận được đề xuất của các vị đại thần, nhà vua lập ra ~q~ kế hoạch, trong kế hoạch thứ ~i~, những lời đề xuất của các vị đại thần từ ~l_i~ đến ~r_i~ sẽ được chấp nhận. Để đánh giá độ hiệu quả của một kế hoạch, nhà vua muốn biết rằng sau khi sát nhập, thành phố có dân số nhiều nhất là bao nhiêu.

Với tư cách là tân trạng nguyên của đất nước Alpha, nhà vua đã giao cho bạn công việc khó nhằn này. Bạn hãy giúp nhà vua đánh giá độ hiệu quả của các kế hoạch hoặc bị tr...

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~q~ (~1\le n, m, q \le 2\times 10^5~ ).

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^4~ ).

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ (~1\le x_i, y_i \le n~ ) — đề xuất của đại thần ~i~ .

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i, r_i~ (~1\le l_i, r_i \le m~ ) — kế hoạch thứ ~i~ của nhà vua.

Output

Với mỗi kế hoạch, in ra dân số lớn nhất của một thành phố sau khi thực hiện kế hoạch trên một dòng.

Scoring

Sample Input 1

6 7 4
6 4 2 7 1 13
5 3
2 5
2 3
1 2
1 6
4 3
5 4
1 3
5 7
1 4
6 7

Sample Output 1

13
19
13
13

Sample Input 2

2 1 1
1 1
1 2
1 1

Sample Output 2

2