Bạn có tin vào tin đồn không?

Trong một thí nghiệm tâm lý nổi tiếng, người ta cho mọi người xem hai sợi dây và yêu cầu họ cho biết sợi nào dài hơn. Thực tế, ngoại trừ một người, tất cả những người còn lại đều là người được thí nghiệm sắp đặt trước. Những người này cố tình nói rằng sợi dây ngắn hơn thực ra lại dài hơn. Khi tất cả những người xung quanh đều đưa ra cùng một câu trả lời, người tham gia thí nghiệm thực sự cũng nói rằng sợi dây ngắn hơn là dài hơn. Thí nghiệm này cho thấy con người chịu ảnh hưởng mạnh mẽ từ những người xung quanh, và tin đồn cũng tương tự như vậy.

Tin đồn bắt đầu từ những người lan truyền đầu tiên. Có thể có nhiều người lan truyền đầu tiên, và ngoại trừ những người này, không ai tự tạo ra và tin vào tin đồn.

Mỗi phút, người tin vào tin đồn sẽ đồng thời lan truyền nó cho tất cả những người xung quanh, và một người trong đám đông sẽ bắt đầu tin vào tin đồn khi có ít nhất một nửa số người xung quanh họ tin vào tin đồn đó.

Vì từ khoảnh khắc bắt đầu tin vào tin đồn, họ sẽ không nghe theo lời nói khác nữa, nên một khi đã tin thì sẽ tiếp tục tin mãi.

Hãy tìm thời điểm mà mỗi người bắt đầu tin vào tin đồn lần đầu tiên.

Dữ liệu vào

Dòng đầu tiên chứa số người $N$. ($1 \le N \le 200\,000$), nghĩa là có $N$ người được đánh số từ 1 đến $N$.

Từ dòng thứ hai trở đi, có $N$ dòng. Dòng thứ $i$ ($1 \le i \le N$) chứa số hiệu những người xung quanh của người thứ $i$ và kết thúc bằng số $0$ để biểu thị kết thúc dòng, các số được phân cách bằng khoảng trắng. Số hiệu là số tự nhiên từ 1 đến $N$, và không có số hiệu nào bị lặp lại trong cùng một dòng. Không có trường hợp một người tự là người xung quanh của chính mình hoặc mối quan hệ xung quanh là một chiều, và tổng số mối quan hệ xung quanh hai chiều không vượt quá $1\,000\,000$.

Dòng tiếp theo chứa số lượng người lan truyền tin đồn đầu tiên $M$. ($1 \le M \le N$)

Dòng cuối cùng chứa số hiệu của những người lan truyền tin đồn đầu tiên, được phân cách bằng khoảng trắng. Số hiệu của những người lan truyền đầu tiên không bị trùng lặp.

Dữ liệu ra

In ra $N$ số nguyên $t_1, t_2, \dots, t_N$ cách nhau bởi khoảng trắng. $t_i$ là thời gian (phút) mà người thứ $i$ bắt đầu tin vào tin đồn lần đầu tiên, và là $-1$ nếu họ không tin vào tin đồn ngay cả khi đã trôi qua một khoảng thời gian đủ dài. Những người lan truyền đầu tiên được coi là bắt đầu tin vào tin đồn từ phút thứ 0.

Ví dụ

Ví dụ 1

7
2 3 0
1 3 0
1 2 4 0
3 5 0
4 0
0
0
2
1 6

0 1 2 3 4 0 -1

Ví dụ 2

7
2 4 0
1 3 0
2 5 0
1 5 6 0
3 4 6 7 0
4 5 7 0
5 6 0
1
6

4 4 3 2 0 1

Ghi chú

• 0 phút: Những người lan truyền đầu tiên (người số 1, 6) tạo ra tin đồn.
• 1 phút: Người số 1 lan truyền tin đồn cho người số 2 và 3. Người số 2 có 1 trong 2 người xung quanh tin vào tin đồn nên bắt đầu tin. Người số 3 chỉ có 1 trong 3 người xung quanh tin vào tin đồn nên không tin. Người số 6 không có người xung quanh để lan truyền.
• 2 phút: Người số 1 và 2 lan truyền tin đồn cho người số 3. Trong 3 người xung quanh, có 2 người (hơn một nửa) tin vào tin đồn, nên người số 3 cũng bắt đầu tin từ phút thứ 2.
• 3 phút: Người số 3 lan truyền tin đồn cho người số 4. Người số 4 bắt đầu tin.
• 4 phút: Người số 5 cũng bắt đầu tin vào tin đồn. Người số 7 không tin vào tin đồn ngay cả khi đã trôi qua một khoảng thời gian đủ dài.