Quốc gia Z có N thành phố được đánh số từ 1 đến N.

Ban đầu, giữa các thành phố có M con đường hai chiều. Mỗi con đường cho phép di chuyển bằng ô tô giữa hai thành phố với thời gian đúng bằng C phút.

Ngoài ra, quốc gia còn có K sân bay. Mỗi sân bay được đặt tại một thành phố khác nhau. Nếu hai thành phố đều có sân bay, người dân có thể di chuyển bằng máy bay trực tiếp giữa hai thành phố đó với thời gian đúng bằng T phút.

Chính phủ cần xử lý Q yêu cầu phát triển hạ tầng. Các yêu cầu được thực hiện lần lượt theo đúng thứ tự trong input.

Có ba loại yêu cầu:

1 X Y C: xây dựng thêm một con đường hai chiều giữa hai thành phố X và Y, thời gian di chuyển bằng ô tô là C phút.
2 X: xây dựng một sân bay mới tại thành phố X. Dữ liệu đảm bảo trước đó thành phố X chưa có sân bay.
3: yêu cầu tính tổng thời gian di chuyển ngắn nhất giữa mọi cặp thành phố.

Gọi F(i, j) là thời gian ngắn nhất để đi từ thành phố i đến thành phố j bằng cách sử dụng các con đường và chuyến bay hiện có.

Nếu không có cách đi từ i đến j, hoặc i = j, thì F(i, j) = 0.

Với mỗi yêu cầu loại 3, hãy tính:

Yêu cầu

Hãy mô phỏng các yêu cầu loại 1 và loại 2, đồng thời in kết quả cho mỗi yêu cầu loại 3.

Input

• 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 chứa K số nguyên phân biệt A_1, A_2, ..., A_K, là các thành phố ban đầu có sân bay.
• M dòng tiếp theo, mỗi dòng chứa ba số nguyên U, V, C, cho biết có một con đường hai chiều nối thành phố U và thành phố V với thời gian di chuyển C phút
• \((1 \le U,V \le N,\ U \ne V,\ 1 \le C \le 10^9)\).
• Q dòng tiếp theo, mỗi dòng mô tả một yêu cầu:
• 1 X Y C \((1 \le X,Y \le N,\ X \ne Y,\ 1 \le C \le 10^9)\).
• 2 X \((1 \le X \le N)\).
• 3.

Output

• Với mỗi yêu cầu loại 3, in ra một số nguyên trên một dòng là tổng thời gian di chuyển ngắn nhất giữa mọi cặp thành phố tại thời điểm đó.

Example

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

600 
320

F(1,1)+F(1,2)+F(1,3) 
+F(2,1)+F(2,2)+F(2,3) 
+F(3,1)+F(3,2)+F(3,3) 
= 0+150+50+150+0+100+50+100+0 
= 600