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 f0,f1,...,fn-1, where fi - the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0,w1,...,wn-1, where wi - the arc weight from i to fi.
The graph from the first sample test.
Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:
si - the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i; mi - the minimal weight from all arcs on the path with length k which starts from the vertex i.
The length of the path is the number of arcs on this path.

The first line contains two integers n,k (1 \le n \le 105,1 \le k \le 1010). The second line contains the sequence f0,f1,...,fn-1 (0 \le fi \lt n) and the third - the sequence w0,w1,...,wn-1 (0 \le wi \le 108).

Print n lines, the pair of integers si, mi in each line.