Đất nước HNAMS gồm ~n~ thành phố nối với nhau bằng ~m~ con đường hai chiều. Con đường thứ ~i~ ~(1 \le i \le m)~ nối hai thành phố ~u_i~ và ~v_i~ có độ dài ~w_i~.

HNAMS đang đối mặt với đại dịch Chow, với ~k~ thành phố bị nhiễm đại dịch, gọi đây là tập ~P~. Tuy nhiên, việc lưu thông giữa các thành phố vẫn cần được thực hiện, vậy nên chính phủ muốn tìm ra một giải pháp an toàn nhất để lưu thông. Gọi ~d(u)~ là khoảng cách ngắn nhất giữa thành phố ~u~ với một thành phố trong tập ~P~. Giả sử bạn muốn đi từ thành phố ~s~ tới ~t~, lộ trình mà bạn đi qua lần lượt gồm các thành phố ~\{u_1 = s, u_2, ..., u_k = t\}~, thì độ an toàn của tuyến đường này sẽ là ~min_{i=1}^k(d(u_i))~.

Chính phủ đang xem xét về ~q~ cặp thành phố trọng điểm, cặp thứ ~i~ là hai thành phố ~s_i~ và ~t_i~. Với mỗi cặp thành phố, chính phủ cần đánh giá xem mức độ an toàn của chúng là bao nhiêu, con số này sẽ được tính bằng cách chọn ra một lộ trình giữa ~s_i~ và ~t_i~, sao cho độ an toàn của lộ trình này là lớn nhất.

Chow là một đại dịch rất nguy hiểm, hãy giúp chính phủ nhanh chóng tính toán độ an toàn cho các cặp thành phố!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~.
• ~m~ dòng sau, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u_i,v_i,w_i~.
• Dòng tiếp theo gồm số nguyên dương ~k~.
• Dòng sau gồm ~k~ số nguyên dương ~u_1,u_2,...,u_k~ miêu tả các thành phố trong tập ~P~.
• Dòng tiếp theo gồm số nguyên dương ~q~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~s_i,t_i~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra kết quả.

Constraints .

• ~1 \le n,q \le 10^5~.
• ~1 \le m \le 5*10^5~.
• ~1 \le w_i \le 10^9~.

Subtask

• Sub ~1~ ~(20\%)~: ~1 \le n \le 20, 1 \le m,q \le 200~.
• Sub ~2~ ~(30\%)~: ~q = 1~.
• Sub ~3~ ~(50\%)~: Không có ràng buộc gì thêm.

Sample Input 1

9 11
1 9 4
1 2 5
2 3 4
4 3 6
2 4 5
3 6 3
8 7 10
6 7 5
5 8 3
9 5 7
5 4 11
2
4 7
6
1 6
5 3
4 8
5 8
1 5
3 6

Sample Output 1

5
5
0
10
10
5

Chán ngán với các trận chiến cũng như nắm bắt được cơ hội kinh doanh, Satoshi cùng chú pokemon của anh ấy - Pikachu đã lập ra một cửa hàng dịch vụ sạc xe điện.

Một ngày nọ, cửa hàng nhận được ~n~ yêu cầu sạc xe, chiếc xe thứ ~i~ cần ~a_i~ phút để sạc đầy bình. Để công việc diễn ra nhanh chóng, Satoshi sẽ chia ~n~ xe ra thành các nhóm tương ứng với các đoạn con liên tiếp theo số lượng tùy ý. Sau đó, anh ấy sẽ để Pikachu sạc điện cho lần lượt từng nhóm xe. Giả sử nhóm thứ ~i~ gồm các xe có chỉ số trong đoạn ~[l_i,r_i]~, tất cả các xe trong nhóm ~i~ sẽ mất ~charge(i) = max_{j \in [l_i,r_i]}(a_j)~ phút để được sạc.

Gọi ~group(i)~ là nhóm của người thứ ~i~. Thời gian chờ của người thứ ~i~, còn được gọi là ~wait(i)~ được tính bằng tổng thời gian sạc của các nhóm xe trước đó (các nhóm xe có chỉ số bé hơn ~group(i)~) cộng với thời gian sạc của nhóm xe ~group(i)~. Nói cách khác, ~wait(i) = \sum_{j=1}^{group(i)} charge(j)~.

Hãy giúp Satoshi tìm được cách phân chia nhóm tối ưu nhất sao cho tổng thời gian chờ đợi của toàn bộ các khách hàng là nhỏ nhất. Nói cách khác, hãy tối ưu cách chia nhóm sao cho ~\sum_i^n wait(i)~ là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.
  
  

Output

• In ra tổng thời gian chờ đợi nhỏ nhất.
  
  

Constraints

• ~1 \le N \le 10^6~.
• ~1 \le a_i \le 10^9~.
  
  

Subtasks

• Subtask ~1~ ~(20\%)~: ~1 \le n \le 1500~ và ~a_i~ không giảm.
• Subtask ~2~ ~(20\%)~: ~a_i~ không giảm.
• Subtask ~3~ ~(20\%)~: ~a_i~ không tăng.
• Subtask ~4~ ~(20\%)~: ~1 \le n \le 1500~.
• Subtask ~5~ ~(20\%)~: Không có ràng buộc gì thêm.
  
  

Sample Test

Input:

5
1 3 2 6 1

Output:

27

Giải thích: Chia thành hai nhóm ~(1,3,2)~ và ~(6,1)~. Nhóm một mất ~3~ phút để sạc và nhóm ~2~ mất ~6~ phút. Vậy các xe ở nhóm ~1~ phải chờ ~3~ phút và các xe ở nhóm hai phải chờ ~9~ phút.

Đáp án là ~3 + 3 + 3 + 9 + 9 = 27~.

Cho một dãy ~p_1,p_2,...,p_n~ là một hoán vị của ~1,2,...,n~. Bạn được thực hiện hai phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi,loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa dãy hoán vị ~p_1,p_2,...,p_n~ về dãy hoán vị ~1,2,3...,n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~p_1,p_2,...,p_n~.

Output

• In ra số bước ít nhất để đưa dãy ~p~ về hoán vị ~1,2,3,...,n~.

Constraints .

• ~1 \le N \le 10^5~.

Subtask

• Sub ~1~ ~(10\%)~: ~n = 3~.
• Sub ~2~ ~(20\%)~: ~n \le 30~.
• Sub ~3~ ~(20\%)~: ~n \le 300~.
• Sub ~4~ ~(20\%)~: ~n \le 1000~.
• Sub ~5~ ~(15\%)~: ~n \le 10^4~.
• Sub ~6~ ~(15\%)~: ~n \le 10^5~.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

3