Xe cứu thương

Một thành phố có \(N\) điểm dân cư đánh số từ \(1\) đến \(N\), được kết nối bởi \(M\) con đường hai chiều. Con đường thứ \(i\) nối từ điểm \(u_i\) đến điểm \(v_i\) có độ dài là \(w_i\) (đơn vị độ dài) và thời gian di chuyển là \(t_i\) (đơn vị thời gian) (\(1 \le u_i, v_i \le N\); \(1 \le w_i, t_i \le 100\) với mọi \(i = 1, 2, \ldots, M\)). Xe cứu thương (chạy điện) có thể di chuyển từ điểm dân cư này sang tất cả các điểm dân cư khác thông qua các con đường trên.

Khi có yêu cầu, xe cứu thương ở vị trí hiện tại sẽ di chuyển tới đón bệnh nhân và đưa tới bệnh viện phù hợp. Theo thông số kỹ thuật, pin của xe không cho phép di chuyển quá \(L\) (đơn vị độ dài).

Trung tâm điều phối nhận thông tin và giao nhiệm vụ cho \(Q\) xe cứu thương khác nhau. Xe cứu thương thứ \(j\) đang ở vị trí \(X_j\) được giao nhiệm vụ từ điểm \(Y_j\) đón bệnh nhân rồi đưa tới bệnh viện ở điểm \(Z_j\) (\(X_j, Y_j, Z_j \le N\) với mọi \(j = 1, 2, \ldots, Q\)).

Yêu cầu: Với mỗi xe cứu thương, hãy xác định thời gian di chuyển ngắn nhất để xe đó có thể tới đón và đưa bệnh nhân tới bệnh viện mà không phải dừng lại sạc pin.

Input

Dữ liệu vào:

• Dòng đầu tiên chứa \(3\) số nguyên dương \(N, M, L\) (\(N \le 100\); \(M \le 1000\); \(L < 1024\)).

• \(M\) dòng tiếp theo, dòng thứ \(i\) (\(i = 1, 2, \ldots, M\)) chứa \(4\) số nguyên \(u_i, v_i, w_i, t_i\) xác định con đường thứ \(i\).

• Dòng tiếp theo chứa số nguyên dương \(Q\).

• \(Q\) dòng cuối, dòng thứ \(j\) (\(j = 1, 2, \ldots, Q\)) chứa \(3\) số nguyên \(X_j, Y_j, Z_j\) xác định vị trí và nhiệm vụ của xe thứ \(j\).

Ràng buộc:

• Subtask 1 (\(30\%\) số điểm): \(Q \le 100\), \(L = 1\), \(X_j = Y_j\) với mọi \(j\).

• Subtask 2 (\(40\%\) số điểm): \(Q \le 100\), \(L = 2\).

• Subtask 3 (\(20\%\) số điểm): \(Q \le 5\).

• Subtask 4 (\(10\%\) số điểm): \(Q \le 10^4\).

Output

In ra \(Q\) dòng, dòng thứ \(j\) là thời gian di chuyển ngắn nhất để xe \(j\) di chuyển đón và đưa bệnh nhân tới bệnh viện. Biết thời gian đưa bệnh nhân lên xe không đáng kể. Trường hợp xe bắt buộc cần dừng lại sạc pin thì đưa ra \(-1\).

Example

Input:

4 5 21
1 4 10 3
4 2 6 9
1 2 20 10
2 3 5 2
1 3 7 9
3
1 1 2
3 2 1
4 1 2

Output:

10
13
-1

Note

Xe thứ nhất đang ở điểm dân cư \(1\) đón luôn bệnh nhân ở điểm đó rồi đi trực tiếp tới \(2\).

Xe thứ hai đi theo lộ trình \(3 \to 2 \to 3 \to 1\). Không thể đi \(3 \to 2 \to 1\) do không đủ pin.

Xe thứ ba không thể thực hiện được do không đủ pin.