Một Trung tâm nghiên cứu tuyệt mật có \(n\) phòng thí nghiệm đặt ngầm trong lòng đất, đánh số từ \(1\) đến \(n\) (\(1 \le n \le 10^{5}\)). Giữa một số phòng có đường hầm hai chiều, mỗi đường hầm mất \(1\) đơn vị thời gian để đi qua. Không có đường hầm nối một phòng với chính nó, nhưng có thể có nhiều đường hầm cùng nối một cặp phòng. Tổng cộng có \(m\) đường hầm (\(1 \le m \le 10^{5}\)). Từ mọi phòng có thể đi đến mọi phòng khác. Có \(k\) phòng có lối thoát hiểm (\(1 \le k \le n\)). Khi sơ tán khẩn cấp, tất cả nhân viên phải tập trung về một phòng có lối thoát hiểm gần nhất.

Mục tiêu: với mỗi phòng \(i\), hãy xác định thời gian tối thiểu để đi tới một phòng có lối thoát hiểm.

Input

• Dòng đầu tiên: hai số nguyên \(n\) và \(k\).
• Dòng thứ hai: \(k\) số nguyên khác nhau — các phòng có lối thoát hiểm.
• Dòng thứ ba: số nguyên \(m\).
• \(m\) dòng tiếp theo: mỗi dòng chứa hai số nguyên mô tả một đường hầm nối trực tiếp giữa hai phòng.

Output

• In ra một dòng gồm \(n\) số nguyên. Số thứ \(i\) là thời gian tối thiểu để nhân viên ở phòng \(i\) đi tới bất kỳ phòng có lối thoát hiểm.

Example

10 2
10 8
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2

1 4 1 2 1 3 2 0 3 0