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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 7;
long long n, m, erzi[N][62], sum[N][62], mina[N][62], k;
long long get_power[62];
void read(long long &x) {
  x = 0;
  char ch = getchar();
  long long pd = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') pd = -pd;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x = x * pd;
}
void write(const long long &x) {
  long long tmp = x;
  long long s = 0;
  char g[10001];
  if (tmp == 0) {
    putchar('0');
    return;
  }
  if (tmp < 0) {
    tmp = -tmp;
    putchar('-');
  }
  while (tmp > 0) {
    g[s++] = tmp % 10 + '0';
    tmp /= 10;
  }
  while (s > 0) {
    putchar(g[--s]);
  }
}
signed main() {
  read(n);
  read(k);
  for (register long long i = 1; i <= n; ++i) {
    read(erzi[i][0]);
    erzi[i][0]++;
  }
  for (register long long i = 1; i <= n; ++i) {
    read(sum[i][0]);
    mina[i][0] = sum[i][0];
  }
  get_power[0] = 1;
  for (register long long i = 1; i <= 60; ++i) {
    get_power[i] = get_power[i - 1] << 1;
  }
  for (register long long i = 1; i <= 60; ++i) {
    for (register long long j = 1; j <= n; ++j) {
      erzi[j][i] = erzi[erzi[j][i - 1]][i - 1];
      sum[j][i] = sum[erzi[j][i - 1]][i - 1] + sum[j][i - 1];
      mina[j][i] = min(mina[erzi[j][i - 1]][i - 1], mina[j][i - 1]);
    }
  }
  for (register long long i = 1; i <= n; ++i) {
    long long ff = i, leave = k, get_sum = 0, get_min = 0x7fffffff;
    for (register long long j = 60; j >= 0; --j) {
      if (get_power[j] <= leave) {
        leave -= get_power[j];
        get_sum += sum[ff][j];
        get_min = min(get_min, mina[ff][j]);
        ff = erzi[ff][j];
      }
    }
    write(get_sum);
    putchar(' ');
    write(get_min);
    puts("");
  }
}