Problem: 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.

<image> 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.

Input

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

Output

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

Examples

Input

7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3


Output

10 1
8 1
7 1
10 2
8 2
7 1
9 3


Input

4 4
0 1 2 3
0 1 2 3


Output

0 0
4 1
8 2
12 3


Input

5 3
1 2 3 4 0
4 1 2 14 3


Output

7 1
17 1
19 2
21 3
8 1

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class problem_0702e {
	static final int HEIGHT = 35;
	static class Node{
		Node[] nexts = new Node[HEIGHT];
		long[] sum = new long[HEIGHT];
		long[] mins = new long[HEIGHT];
		int cyclen = -1;
		long sumQuery(long k){
			if(k == 0) return 0;
			int nbits = Long.bitCount(Long.highestOneBit(k)-1);
			return sum[nbits] + nexts[nbits].sumQuery(k - Long.highestOneBit(k));
		}
		long rangeMinQuery(long k){
			if(k == 0) return Long.MAX_VALUE;
			int nbits = Long.bitCount(Long.highestOneBit(k)-1);
			return Math.min(mins[nbits], nexts[nbits].rangeMinQuery(k - Long.highestOneBit(k)));
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader
				(new InputStreamReader(System.in));
		String[] line;
		
		line = br.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		long K = Long.parseLong(line[1]);
		
		nodes = new Node[N];
		for(int i=0;i<N;i++){
			nodes[i] = new Node();
		}
		line = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			int point = Integer.parseInt(line[i]);
			nodes[i].nexts[0] = nodes[point];
		}
		line = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			long w = Integer.parseInt(line[i]);
			nodes[i].sum[0] = w;
			nodes[i].mins[0] = w;
		}
		
		for(int h = 0; h < HEIGHT-1; h++){
			for(int n = 0; n < N; n++){
				if(nodes[n].nexts[h] == null) continue;
				nodes[n].nexts[h+1] = nodes[n].nexts[h].nexts[h];
				nodes[n].sum[h+1] = nodes[n].sum[h] + nodes[n].nexts[h].sum[h];
				nodes[n].mins[h+1] = Math.min(nodes[n].mins[h], nodes[n].nexts[h].mins[h]);
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int n=0;n<N;n++){
			sb.append((nodes[n].sumQuery(K)+" ")+(nodes[n].rangeMinQuery(K)+"\n"));
		}
		System.out.print(sb);
	}
	
	static Node[] nodes;
}