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.io.InputStream;

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

  static class TaskE {
    int n;
    long k;
    int[] toIdx;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      k = in.nextLong();
      toIdx = new int[n];
      for (int i = 0; i < n; ++i) {
        toIdx[i] = in.nextInt();
      }
      int[][] currentPosition = new int[2][n];
      long[][] currentSum = new long[2][n];
      int[][] currentMin = new int[2][n];
      int currentT = 0;
      int[][] nextPosition = new int[2][n];
      long[][] nextSum = new long[2][n];
      int[][] nextMin = new int[2][n];
      int nextT = 0;
      for (int i = 0; i < n; ++i) {
        currentPosition[currentT][i] = i;
        currentSum[currentT][i] = 0;
        currentMin[currentT][i] = Integer.MAX_VALUE;
        int w = in.nextInt();
        nextPosition[nextT][i] = toIdx[i];
        nextSum[nextT][i] = w;
        nextMin[nextT][i] = w;
      }
      for (long bit = 1; bit <= k; bit <<= 1) {
        if ((k & bit) > 0) {
          for (int i = 0; i < n; ++i) {
            currentPosition[currentT ^ 1][i] = nextPosition[nextT][currentPosition[currentT][i]];
            currentSum[currentT ^ 1][i] = currentSum[currentT][i] + nextSum[nextT][currentPosition[currentT][i]];
            currentMin[currentT ^ 1][i] = Math.min(currentMin[currentT][i], nextMin[nextT][currentPosition[currentT][i]]);
          }
          currentT ^= 1;
        }
        if ((bit << 1) <= k) {
          for (int i = 0; i < n; ++i) {
            nextPosition[nextT ^ 1][i] = nextPosition[nextT][nextPosition[nextT][i]];
            nextSum[nextT ^ 1][i] = nextSum[nextT][i] + nextSum[nextT][nextPosition[nextT][i]];
            nextMin[nextT ^ 1][i] = Math.min(nextMin[nextT][i], nextMin[nextT][nextPosition[nextT][i]]);
          }
          nextT ^= 1;
        }
      }
      for (int i = 0; i < n; ++i) {
        out.printf("%d %d\n", currentSum[currentT][i], currentMin[currentT][i]);
      }
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPostion;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPostion = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public long nextLong() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      long res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPostion >= numberOfChars) {
        currentPostion = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPostion++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' '
          || c == '\n'
          || c == '\r'
          || c == '\t'
          || c < 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

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

    public void printf(String format, Object... objects) {
      writer.printf(format, objects);
    }

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

  }
}