Một khu vực có ~n~ thành phố (đánh số ~1~ đến ~n~) và ~m~ con đường hai chiều, đường thứ ~i~ nối hai thành phố ~u_i, v_i~ với thời gian di chuyển ~w_i~ (nguyên dương), mạng lưới đường liên thông và trung tâm chỉ huy đặt tại thành phố ~S~.

Trung tâm tính thời gian di chuyển ngắn nhất từ ~S~ tới mọi thành phố khác. Với mỗi thành phố ~v \ne S~, xác định một "tuyến cứu hộ chuẩn" duy nhất tới ~v~ như sau: Gọi ~t[v]~ là thời gian ngắn nhất tới ~v~, xét tất cả thành phố ~u~ sao cho có con đường trực tiếp ~(u, v)~ với thời gian ~w~ thỏa ~t[u] + w = t[v]~ (tức đi qua ~u~ là một cách đạt thời gian ngắn nhất tới ~v~) - trong số các ~u~ thỏa điều kiện này, chọn ~u~ nhỏ nhất làm "trạm liền trước" của ~v~ trên tuyến cứu hộ (gọi ~u~ là cha cứu hộ của ~v~). Quy tắc này áp dụng cho mọi thành phố nên xác định duy nhất một cây cứu hộ gốc tại ~S~.

Sau khi xây xong cây cứu hộ, có ~q~ sự kiện xảy ra tuần tự theo thời gian, mỗi sự kiện thuộc một trong hai loại:

• Loại 1: "1 u x" - cấp ~x~ đơn vị vật tư cho thành phố ~u~ (cộng dồn vào lượng vật tư hiện có tại ~u~, lượng vật tư ban đầu của mọi thành phố là ~0~).

• Loại 2: "2 u v" - hỏi tổng lượng vật tư (đã cập nhật đến thời điểm này) của tất cả các thành phố nằm trên đường đi từ ~u~ đến ~v~ trên cây cứu hộ.

Yêu cầu: Với mỗi sự kiện loại ~2~, in ra kết quả tìm được.

Input

• Dòng ~1~: bốn số nguyên ~n, m, S, q~ ~(1 \le n \le 2 \cdot 10^5; n - 1 \le m \le 4 \cdot 10^5; 1 \le S \le n; 1 \le q \le 2 \cdot 10^5)~;

• ~m~ dòng tiếp theo, mỗi dòng ba số nguyên ~u_i, v_i, w_i~ - con đường hai chiều nối thành phố ~u_i, v_i~ với thời gian ~w_i~ ~(1 \le i \le m; 1 \le u_i, v_i \le n; 1 \le w_i \le 10^9)~;

• ~q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo đúng định dạng nêu trên ("1 u x" hoặc "2 u v"; ~1 \le u, v \le n; 1 \le x \le 10^9~).

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Output

~q~ dòng: mỗi dòng một số nguyên tương ứng với mỗi sự kiện loại ~2~ - kết quả tìm được theo đúng thứ tự xuất hiện trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

17
20

Notes

Từ thành phố ~1~: ~t[2] = 2~, ~t[3] = 4~ (qua ~2~), ~t[4] = 5~ (qua ~3~), ~t[5] = 6~ (qua ~4~). Cây cứu hộ là một chuỗi thẳng ~1-2-3-4-5~. Sự kiện "1 5 10" và "1 3 7" cấp vật tư cho ~5~ và ~3~. Truy vấn "2 5 1" hỏi đường đi ~5-4-3-2-1~: tổng vật tư ~= 10~ (tại ~5~) ~+ 0 + 7~ (tại ~3~) ~+ 0 + 0 = 17~. Sau đó "1 2 3" cấp thêm cho thành phố ~2~. Truy vấn "2 5 2" hỏi đường đi ~5-4-3-2~: tổng ~= 10 + 0 + 7 + 3 = 20~.