You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.
Graph is given as the array f_{0}, f_{1}, ..., f_{n - 1}, where f_{i} — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w_{0}, w_{1}, ..., w_{n - 1}, where w_{i} — the arc weight from i to f_{i}.
Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers s_{i} and m_{i}, where:
The length of the path is the number of arcs on this path.
The first line contains two integers n, k (1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 10^{10}). The second line contains the sequence f_{0}, f_{1}, ..., f_{n - 1} (0 ≤ f_{i} < n) and the third — the sequence w_{0}, w_{1}, ..., w_{n - 1} (0 ≤ w_{i} ≤ 10^{8}).
Print n lines, the pair of integers s_{i}, m_{i} in each line.
7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3
10 1
8 1
7 1
10 2
8 2
7 1
9 3
4 4
0 1 2 3
0 1 2 3
0 0
4 1
8 2
12 3
5 3
1 2 3 4 0
4 1 2 14 3
7 1
17 1
19 2
21 3
8 1
Name |
---|