Xây dựng tuyến đường giao thông

Quốc gia \(Z\) có \(N\) thành phố được nối với nhau bởi \(M\) con đường hai chiều và \(K\) sân bay. Khi đi qua một con đường nối hai thành phố \(U\) và \(V\) (\(1 \le U, V \le N\)) bằng ô tô thì sẽ mất thời gian là \(C\) phút. Mỗi thành phố có tối đa một sân bay và bất cứ chuyến bay nào (giữa hai thành phố đều có sân bay) đều có thời gian di chuyển mất \(T\) phút.

Lãnh đạo quốc gia \(Z\) đưa ra \(Q\) yêu cầu để đẩy mạnh phát triển cơ sở hạ tầng. Yêu cầu sau chỉ được thực hiện khi yêu cầu trước đó đã hoàn thành. Mỗi yêu cầu của lãnh đạo có thể thực hiện một trong ba loại công việc sau:

• Loại 1: Xây dựng một con đường hai chiều mới giữa hai thành phố \(U\) và \(V\) (\(1 \le U, V \le N\)) sao cho mất \(C\) phút khi di chuyển bằng ô tô.

• Loại 2: Xây dựng một sân bay mới ở một thành phố \(X\) (\(1 \le X \le N\)).

• Loại 3: Tính \(\sum_{i=1}^{N}\sum_{j=1}^{N} f(i,j)\) với \(f(i,j)\) là tổng thời gian tối thiểu để đi từ thành phố \(i\) đến thành phố \(j\) qua các con đường và chuyến bay (nếu không có cách đi hoặc \(i = j\) thì \(f(i,j) = 0\)).

Yêu cầu: Giúp lãnh đạo mô hình hóa các yêu cầu loại 1 và 2, cho biết kết quả của các yêu cầu loại 3 tương ứng.

Input

Dữ liệu vào có cấu trúc:

• Dòng đầu tiên chứa năm số nguyên \(N, M, Q, K, T\) (\(1 \le N, Q \le 400\); \(0 \le K \le N\); \(1 \le M \le 10^5\); \(1 \le T \le 10^9\)).

• Dòng thứ hai gồm \(K\) số nguyên đôi một phân biệt \(A_i\) (\(1 \le A_i \le N\)) cho biết các thành phố có sân bay (dòng này để trống nếu \(K = 0\)).

• \(M\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(U, V, C\) cho biết có con đường nối hai thành phố \(U\) và \(V\) với thời gian di chuyển là \(C\) phút (\(1 \le U, V \le N\); \(U \ne V\); \(1 \le C \le 10^9\)).

• \(Q\) dòng cuối cùng, mỗi dòng được viết theo một trong ba định dạng tương ứng với ba loại yêu cầu:

  • Loại 1: 1 X Y C: xây dựng một con đường mới nối hai thành phố \(X\) và \(Y\) với thời gian di chuyển bằng ô tô là \(C\) (\(1 \le X, Y \le N\); \(X \ne Y\); \(1 \le C \le 10^9\)).

• Loại 2: 2 X: xây dựng một sân bay mới tại thành phố \(X\) (\(1 \le X \le N\)). Dữ liệu đảm bảo \(X\) chưa có sân bay trước yêu cầu này.

• Loại 3: 3: tính tổng thời gian tối thiểu.

Ràng buộc:

• Có \(10\%\) số điểm tương ứng với \(N, Q \le 100\); \(M \le 200\); \(K = 0\), không có yêu cầu loại 2.

• Có \(20\%\) số điểm tương ứng với \(N, Q \le 100\).

• Có \(30\%\) số điểm tương ứng với \(K = 0\) và không có yêu cầu loại 2.

• Có \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Output

In ra với mỗi yêu cầu loại 3, ghi một số nguyên trên một dòng là kết quả tương ứng.

Example

Input:

3 1 3 2 100
2 3
1 3 50
3
1 2 3 30
3

Output:

600
320

Note

Yêu cầu loại 3 thứ nhất: \(f(1,2) = 50 + 100 = 150\), \(f(1,3) = 50\), \(f(2,1) = 150\), \(f(2,3) = 100\), \(f(3,1) = 50\), \(f(3,2) = 100\), tổng bằng \(600\).

Yêu cầu loại 3 thứ hai (sau khi xây thêm đường \(2\)--\(3\) mất \(30\) phút): \(f(1,2) = 50 + 30 = 80\), \(f(1,3) = 50\), \(f(2,3) = 30\) và các giá trị đối xứng, tổng bằng \(320\).