Đường đi ngắn nhất theo thời gian (Single Source Shortest Path, Time Table)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một đồ thị có hướng gồm $n$ đỉnh, đánh số từ $0$ đến $n-1$. Bạn bắt đầu tại đỉnh $s$ ở thời điểm $0$.

Mỗi cạnh có dạng $(u,v,t_0,P,d)$. Cạnh đi từ $u$ đến $v$, thời gian di chuyển là $d$. Tuy nhiên, bạn chỉ có thể bắt đầu đi qua cạnh tại các thời điểm hợp lệ:

• $t_0$;
• $t_0+P$;
• $t_0+2P$;
• $\ldots$

Nếu $P=0$, cạnh chỉ có đúng một chuyến khởi hành tại thời điểm $t_0$.

Nếu đến $u$ trước chuyến khởi hành tiếp theo, bạn được phép chờ tại $u$. Với mỗi truy vấn, hãy xác định thời điểm sớm nhất có thể đến đỉnh được hỏi.

Input

Dòng đầu chứa bốn số nguyên $n,m,q,s$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $u,v,t_0,P,d$ mô tả một cạnh có hướng.

Trong $q$ dòng cuối, mỗi dòng chứa một đỉnh $x$ cần truy vấn.

Mỗi file Input của Phước Hưng OJ chứa đúng một test case; không có dòng kết thúc 0 0 0 0.

Output

Với mỗi truy vấn, in ra thời điểm sớm nhất có thể đến đỉnh tương ứng. Nếu không thể đến, in Impossible.

Subtask

• Subtask 1 — 20% — 0.50 giây: $1\le n\le100$; $0\le m\le500$; $1\le q\le20$.
• Subtask 2 — 30% — 1.00 giây: $1\le n\le2000$; $0\le m\le6000$; $1\le q\le100$.
• Subtask 3 — 50% — 2.00 giây: $1\le n\le10^4$; $0\le m\le3\cdot10^4$; $1\le q\le100$; $0\le t_0,P,d\le10^9$.

Ví dụ

Input

4 4 4 0
0 1 0 5 3
0 2 2 0 4
1 3 4 5 2
2 3 8 0 1
0
1
2
3

Output

0
3
6
6

Giải thích

Từ đỉnh $0$, có thể đến đỉnh $1$ lúc $3$, đỉnh $2$ lúc $6$. Để tới đỉnh $3$, phương án tốt nhất cho kết quả thời điểm $6$. Đỉnh nguồn $0$ có thời điểm đến bằng $0$.