Thành phố H được biết đến với cái tên “thiên đường tội phạm” có ~n~ (~n \le 2 \times 10^5~) giao lộ được nối với nhau bằng ~m~ (~m \le 2 \times 10^5~) con đường, đảm bảo tồn tại ít nhất một tuyến đường đi giữa 2 giao lộ bất kì.

Vào mỗi ngày trong ~q~ (~q \le 2 \times 10^5~) ngày liên tiếp, cục cảnh sát nhận được một tin báo rằng sẽ có một nhóm tội phạm di chuyển từ ~u~ tới ~v~. Để ngăn chặn nhóm tội phạm, cục cảnh sát có thể điều động duy nhất 1 nhóm cảnh sát canh giữ tại ~w~ (khác ~u~ và ~v~) với chi phí là ~a[w]~ sao cho mọi đường đi của tội phạm đi ~u~ tới ~v~ đều phải đi qua ~w~.

Yêu cầu: Hãy tìm chi phí nhỏ nhất để ngăn chặn nhóm tội phạm.

Input

• Dòng đầu ghi 2 số ~n, m~ là số giao lộ và số con đường trong thành phố (~n, m \le 2 \times 10^5~).
• Dòng thứ hai ghi ~n~ số ~a[1], a[2], \dots, a[n]~ là chi phí để điều động cảnh sát tới từng giao lộ (~a[i] \le 10^9~).
• Sau đó là ~m~ dòng, mỗi dòng ghi 2 số ~a, b~, thể hiện có 1 con đường nối 2 giao lộ ~a~ và ~b~.
• Dòng tiếp theo ghi số ngày ~q~ có tin báo tội phạm (~q \le 2 \times 10^5~).
• Dòng thứ ~i~ trong ~q~ dòng sau ghi 2 số ~u, v~ (~1 \le u, v \le n~) thể hiện 1 nhóm tội phạm di chuyển từ ~u~ tới ~v~ trong ngày thứ ~i~.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là chi phí nhỏ nhất để ngăn chặn nhóm tội phạm ở ngày thứ ~i~, hoặc -1 nếu không thể ngăn chặn.

Sample Input 1

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

Sample Output 1

1
-1
1
-1
10