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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EAnalysisOfPathesInFunctionalGraph solver = new EAnalysisOfPathesInFunctionalGraph();
        solver.solve(1, in, out);
        out.close();
    }

    static class EAnalysisOfPathesInFunctionalGraph {
        long[][] sum;
        int[][] child;
        long[][] min;

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            long k = in.scanLong();
            sum = new long[n][35];
            child = new int[n][35];
            min = new long[n][35];

            for (int i = 0; i < n; i++) Arrays.fill(child[i], -1);
            int indres[] = new int[n];
            for (int i = 0; i < n; i++) child[i][0] = in.scanInt();
            for (int i = 0; i < n; i++) {
                sum[i][0] = in.scanInt();
                min[i][0] = sum[i][0];
            }

            for (int i = 1; i < 35; i++) {
                for (int node = 0; node < n; node++) {
                    child[node][i] = child[child[node][i - 1]][i - 1];
                }
            }


            for (int i = 1; i < 35; i++) {
                for (int node = 0; node < n; node++) {
                    sum[node][i] = sum[node][i - 1] + sum[child[node][i - 1]][i - 1];
                }
            }


            for (int i = 1; i < 35; i++) {
                for (int node = 0; node < n; node++) {
                    min[node][i] = Math.min(min[node][i - 1], min[child[node][i - 1]][i - 1]);
                }
            }


            for (int i = 0; i < n; i++) {
                out.print(findIT(i, k) + " ");
                out.println(findITMIn(i, k));
            }


        }

        long findIT(int node, long k) {
            if (k == 0) return 0;
            int xx = -1;
            for (int i = 0; i < 35; i++) {
                if ((1l << i) <= k) xx = i;
            }
            return sum[node][xx] + findIT(child[node][xx], k - (1l << xx));
        }

        long findITMIn(int node, long k) {
            if (k == 0) return Integer.MAX_VALUE / 2;
            int xx = -1;
            for (int i = 0; i < 35; i++) {
                if ((1l << i) <= k) xx = i;
            }
            return Math.min(min[node][xx], findITMIn(child[node][xx], k - (1l << xx)));
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

    }
}