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.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

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

    static class EAnalysisOfPathesInFunctionalGraph {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            long k;
            int n;
            int p;
            long[][][] sparseTable;
            n = in.nextInt();
            k = in.nextLong();
            p = (int) (Math.log(k) / Math.log(2));
            sparseTable = new long[n][p + 1][3];
            /*[IndexNo][pthPower][0] -> toWhatNode*/
            /*[IndexNo][pthPower][1] -> sum Along the path*/
            /*[IndexNo][pthPower][2] -> Min along the path*/
            for (int i = 0; i < n; i++) {
                sparseTable[i][0][0] = in.nextInt();
            }
            for (int i = 0; i < n; i++) {
                sparseTable[i][0][2] = sparseTable[i][0][1] = in.nextInt();
            }
            int dest = -1;
            long sum = -1;
            long min = -1;
            for (int j = 1; j <= p; j++) {
                for (int i = 0; i < n; i++) {
                    dest = (int) sparseTable[i][j - 1][0];
                    sum = sparseTable[i][j - 1][1] + sparseTable[dest][j - 1][1];
                    min = _F.min(sparseTable[i][j - 1][2], sparseTable[dest][j - 1][2]);
                    sparseTable[i][j][0] = sparseTable[dest][j - 1][0];
                    sparseTable[i][j][1] = sum;
                    sparseTable[i][j][2] = min;
                }
            }

            for (int i = 0; i < n; i++) {
                long s = 0;
                int m = (int) 1e8;
                int j = i;
                for (int d = 0; 1L << d <= k; d++)
                    if ((k & 1L << d) > 0) {
                        s += sparseTable[j][d][1];
                        m = Math.min(m, (int) sparseTable[j][d][2]);
                        j = (int) sparseTable[j][d][0];
                    }
                out.println(s, m);
            }

            //For debugging
//        for(int k = 0;k<3;k++){
//            if(k==0){
//                out.println("Printing Dests");
//            }else if(k==1){
//                out.println("Printing sums");
//            }else{
//                out.println("Printing mins");
//            }
//            for(int i = 0;i<n;i++){
//                for(int j = 0;j<=p;j++){
//                    out.print(sparseTable[i][j][k]+" ");
//                }
//                out.println();
//            }
//        }


//        for(int i = 0;i<n;i++){
//            int node = i;
//            long d = k;
//            long minn = LINF;
//            long summ = 0;
//            while(d>0){
//                long power = d&-d;
//                int p = (int)(Math.log(power)/Math.log(2));
////            debug("Power - p ",power,p);
//                d-=power;
//                summ+=(sparseTable[node][p][1]);
//                minn = min(minn,sparseTable[node][p][2]);
//                node = (int) sparseTable[node][p][0];
//            }
//            out.println(summ,minn);
//        }


        }

    }

    static class _F {
        public static <T extends Comparable<T>> T min(T... list) {
            T candidate = list[0];
            for (T i : list) {
                if (candidate.compareTo(i) > 0) {
                    candidate = i;
                }
            }
            return candidate;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; ++i) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}