Ở thành phố Miêu Ti, những con người ở đây đều rất mê trà sữa giống xóm "Tà tưa" vậy!!. Để đáp ứng nhu cầu của những con nghiện tà tưa ở đây, có ~n~ điểm buôn để bán trà sữa. Các điểm buôn có thể tới nhau qua một hoặc các con đường trung gian, tuy nhiên giữa ~2~ điểm buôn bất kì duy chỉ có đúng một cách đi tới nhau.

Bạn là kế toán của một công ty sản xuất nguyên liệu trà sữa và nhiệm vụ của bạn là bán ra được những nguyên liệu ấy tới các điểm buôn với một giá tiền nào đó để có thể thu được tiền bán với giá trị lớn nhất. Ở mỗi điểm buôn ~i~, có ra giá trần ~c_i~ để mua nguyên liệu từ bạn, bạn sẽ có thể bán cho điểm buôn ~i~ nếu mức giá của nguyên liệu bạn bán không được quá ~c_i~.

Bạn sẽ thực hiện nhiệm vụ ấy trong ~q~ ngày. Ở ngày thứ ~t~, bạn sẽ thực hiện một chuyến đi qua các điểm buôn, và bán nguyên liệu cho các điểm buôn mà bạn đã đi qua. Chuyến đi là một đường đi đơn, có nghĩa là mỗi điểm buôn đã đi qua thì không được đi lại. Và không phải bạn muốn đi từ điểm buôn nào hay kết thúc ở đâu cũng được, bạn chỉ có thể bắt đầu đi hay kết thúc chuyến đi tại một trong các điểm buôn thuộc ~s_t~.

Do chuyến đi là xuyên suốt vì thế bạn cần xác định trước số lượng nguyên liệu cũng như mức tiền bán nguyên liệu ấy. Và cũng bởi vì là một người trung thực nên mức giá ấy là không đổi ở tất cả các điểm buôn. Ở các điểm buôn mà bạn đã đi qua, trách việc mất khách tại các điểm ấy bạn cũng cần tính toán giá bán sao cho bạn có thể bán tại tất cả những điểm ấy.

Vì tại mỗi điểm buôn đều mua chính xác ~1~ lần nguyên liệu mà bạn bán ra nên có thể nói nếu bạn đi qua ~x~ điểm buôn thì bạn sẽ bán được ~x~ nguyên liệu với một giá tiền ~k~ nào đó. Ở mỗi ngày như vậy, bạn cần đưa ra tổng số tiền bạn kiếm được hay chính là ~x \cdot k~.

Input

Dữ liệu vào bao gồm:

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,q~ — Số lượng điểm buôn, số lượng con đường và số ngày cần giải quyết. (~1 \leq n,m,q \leq 2 \cdot 10^5~)

• Dòng thứ ~2~ gồm ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ — Mức giá sàn để mua sản phẩm của các điểm buôn. (~0 \leq c_i \leq 10^9 ∀i 1 \leq i \leq n~).

• Dòng thứ ~j~ trong số ~m~ dòng tiếp theo gồm ~2~ số nguyên ~u_j, v_j~ — Cho biết có đường đi nối trực tiếp giữa ~2~ điểm buôn ~u_j~ và ~v_j~. (~1 \leq u_j, v_j \leq n~ ~∀j~ ~1 \leq j \leq m~).

• Dòng thứ ~t~ trong số ~Q~ dòng cuối cùng gồm số đầu tiên là ~|s_t|~ theo sau là ~|s_t|~ số nguyên — Cho biết tập hợp các điểm buôn có thể bắt đầu, và kết thúc trong chuyến hành trình tại ngày ~t~. (~x ∈ s_i, 1 \leq x \leq n, \sum ^Q _{t=1} |S_t| \leq 2 \cdot 10^5~).

Output

Gồm ~q~ dòng, in ra đáp án của bài toán trên ~1~ dòng.

Scoring

Sample Input 1

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

Sample Output 1

6
3
9