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;
import java.io.PrintWriter;

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];
//		boolean isSCC = false;
		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];
//		nexts = new ArrayList[N];
		for(int i=0;i<N;i++){
			nodes[i] = new Node();
//			nexts[i] = new ArrayList<>();
		}
		line = br.readLine().split(" ");
		for(int i = 0; i < N; i++){
			int point = Integer.parseInt(line[i]);
			nodes[i].nexts[0] = nodes[point];
//			nexts[i].add(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;
		}
		
//		// run SCC on the graph
//		S = new ArrayDeque<Integer>(N);
//		dfsNum = new int[N]; Arrays.fill(dfsNum, UNV);
//		dfsLow = new int[N]; Arrays.fill(dfsLow, UNV);
//		visited = new boolean[N];
//		dfsNumCounter = numSCC = 0;
//		for(int n=0;n<N;n++){
//			if(dfsNum[n] == UNV){
//				tarjanSCC(n);
//			}
//		}
		
		// build the tree's binlifting elements
		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]);
			}
		}
		
		PrintWriter out = new PrintWriter(System.out);
		for(int n=0;n<N;n++){
			out.println(nodes[n].sumQuery(K)+" "+nodes[n].rangeMinQuery(K));
		}
		out.flush();
	}
	
	static Node[] nodes;
//	static int numSCC = 0;
//	static final int UNV = Integer.MAX_VALUE;
//	static int dfsNumCounter;
//	static ArrayList<Integer>[] nexts;
//	static int[] dfsNum, dfsLow;
//	static boolean[] visited;
//	static ArrayDeque<Integer> S;
//	static void tarjanSCC(int u){
//		dfsLow[u] = dfsNum[u] = dfsNumCounter++;
//		S.push(u);
//		visited[u] = true;
//		for(int j=0;j<(int)nexts[u].size(); j++){
//			int v = nexts[u].get(j).intValue();
//			if(dfsNum[v] == UNV) tarjanSCC(v);
//			if(visited[v]) dfsLow[u] = Math.min(dfsLow[u], dfsLow[v]);
//		}
//		if(dfsLow[u] == dfsNum[u]){
//			ArrayDeque<Node> s = new ArrayDeque<>();
//			while(true){
//				int v = S.pop().intValue(); visited[v] = false;
//				nodes[v].isSCC = true;
//				s.push(nodes[v]);
//				if(u == v) break;
//			}
//			int size = s.size();
//			while(!s.isEmpty()){
//				Node v = s.pop();
//				v.cyclen = size;
//			}
//		}
//	}
}