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.*;
import java.util.*;
import java.math.*;
 
public class E { 
    
    static boolean ONLINE_JUDGE = false;//change before submit
    static Fast f = new Fast();
    static PrintWriter out = new PrintWriter(System.out); 
    static boolean TEST_CASES = false;
    
    
    static void solve(int TC_NO) {

      
       int n = ri();
       long k = rl();
       int[] f = ra(n);
       int[] w = ra(n);

       DS[] ds = new DS[n];

       for(int i = 0; i < n; i++) ds[i] = new DS(f[i],w[i],w[i]);

       DS[] ans = bexpo(ds,k);

       for(int i = 0; i < n; i++){
       	  out.println(ans[i].sum+" "+ans[i].min);
       }

       //out.println();
      /*-----WARNING : change [ONLINE_JUDGE = false] before SUBMIT-----*/ 
    }

    static DS[] bexpo(DS[] ds, long k){
    	DS[] ans = new DS[ds.length];
    	for(int i = 0; i < ans.length; i++) ans[i] = new DS(ds[i].des,ds[i].sum,ds[i].min);
    	k--;
    	while(k>0){
            if(k%2==1) ans = transfer(ans,ds);
            ds = transfer(ds,ds);
            k/=2;
    	}
    	return ans;
    }

    static DS[] transfer(DS[] ds1, DS[] ds2){
    	DS[] ans = new DS[ds1.length];
    	for(int i = 0; i < ans.length; i++){
            int des = ds1[ds2[i].des].des;
            long sum = ds2[i].sum + ds1[ds2[i].des].sum;
            int min = Math.min(ds2[i].min,ds1[ds2[i].des].min);
            ans[i] = new DS(des,sum,min);
    	}

    	return ans;
    }

    static class DS{
    	private int des;
    	private long sum;
    	private int min;

    	public DS(int des, long sum, int min){
    		this.des = des;
    		this.sum = sum;
    		this.min = min; 
    	}
    }

    
    public static void main(String[] args)throws Exception{

      out = ONLINE_JUDGE? new PrintWriter(new BufferedWriter(new FileWriter("output.txt"))): new PrintWriter(System.out);
      

     
      if(TEST_CASES){
          
          int t = ri();
          int i = 1;
          while(i<=t){
            solve(i);
            i++;
          }

      }

      else {

        solve(1);
      
      }
      
      out.close();

    }

    static int ri() {

      return f.nextInt();
    
    }

    static long rl() {
 
      return f.nextLong();
    
    }

    static double rd() {

       return f.nextDouble();
    
    }

    static char rc() {
      
       return rs().charAt(0);

    }

    static String rs() {

      return f.next();

    }

    static String rS() {
      
       return f.nextLine();
    
    }

    static int[] ra(int n) {
        
      int[] a = new int[n];
      for(int i = 0;i<n;i++) a[i] = ri();
      return a;
        
    }

    static long[] ral(int n) {
        
      long[] a = new long[n];
      for(int i = 0;i<n;i++) a[i] = rl();
      return a;
        
    }

    static double[] rad(int n) {

      double[] a = new double[n];
      for(int i = 0;i<n;i++) a[i] = rd();
      return a;

    }

    static char[] rac() {

        char[] c = rs().toCharArray();

        return c;

    }
    
    static int[][] rm(int n, int m) {
       
       int[][] mat = new int[n][m];

       for(int i = 0; i < n; i++) mat[i] = ra(m);
       
       return mat;

    }

    static char[][] rmc(int n) {
      
      char[][] cmat = new char[n][];
      
      for(int i = 0; i < n; i++) cmat[i] = rac();

      return cmat;

    }

    static void sort(int[] a) {

      ArrayList<Integer> list=new ArrayList<>();
      for (int i:a) list.add(i);
      Collections.sort(list);
      for (int i=0; i<a.length; i++) a[i]=list.get(i);

    }

    static String gcc(int TC_NO) {

         return "Case #"+TC_NO+": ";

    }

    static boolean isLetter(char c){

      return (64<c && c<91) || (96<c && c<123);
    
    }
  
    static class Fast{

       public BufferedReader br;
       public StringTokenizer st;
       
       public Fast(){
            try{
                br = ONLINE_JUDGE? (new BufferedReader(new FileReader("input.txt"))):(new BufferedReader(new InputStreamReader(System.in)));
            }
            catch(Exception e){
              throw new RuntimeException(e);
            }
       }
       
       String next(){
            while(st==null || !st.hasMoreTokens()){
                 try{
                      st=new StringTokenizer(br.readLine());
                 }
                 catch(IOException e){
                      throw new RuntimeException(e);
                 }
                 
            }
                 return st.nextToken();
            }
       int nextInt(){
            return Integer.parseInt(next());
       }
   
       long nextLong(){
            return Long.parseLong(next());
       }
   
       double nextDouble(){
            return Double.parseDouble(next());
       }

       String nextLine() 
          { 
              String str = ""; 
              try
              { 
                  str = br.readLine(); 
              } 
              catch (IOException e) 
              { 
                  e.printStackTrace(); 
              } 
              return str; 
          } 
   
    }

}