Thống Kê Trên Đường Chuyển

Có $N$ đỉnh được đánh số từ $0$ đến $N-1$. Từ mỗi đỉnh $i$ có đúng một cạnh đi tới đỉnh $f_i$; trọng số của cạnh này là $w_i$.

Với từng đỉnh xuất phát $s$, hãy đi theo đúng $K$ cạnh liên tiếp. Cần tính tổng trọng số của $K$ cạnh đã đi và trọng số nhỏ nhất trong số các cạnh đó.

Input

• Dòng đầu chứa $N$ và $K$.
• Dòng thứ hai chứa $N$ số $f_0,f_1,\dots ,f_{N-1}$.
• Dòng thứ ba chứa $N$ số $w_0,w_1,\dots ,w_{N-1}$; $w_i$ là trọng số cạnh $i\to f_i$.

Output

• In $N$ dòng; dòng ứng với đỉnh $i$ gồm tổng trọng số và trọng số nhỏ nhất trên hành trình dài $K$ cạnh bắt đầu từ $i$.

Constraints

• $1\le N\le 10^5$.
• $1\le K\le 10^{10}$.
• $0\le f_i<N$.
• $0\le w_i\le 10^8$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 2000$ và $K\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 4
1 2 0 2 4
5 1 7 3 9

18 1
14 1
20 1
16 1
36 9