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;
struct node {
  long long data, Min, N;
} fat[100010][45];
long long head[100010], ver[200010], edge[200010], Next[200010], tot = 0;
void add(long long x, long long y, long long z) {
  ver[++tot] = y;
  edge[tot] = z;
  Next[tot] = head[x];
  head[x] = tot;
}
long long t;
void bfs(long long h) {
  queue<long long> q;
  q.push(h);
  while (!q.empty()) {
    long long x = q.front();
    q.pop();
    if (fat[x][0].data != -1) continue;
    for (long long i = head[x]; i; i = Next[i]) {
      long long y = ver[i];
      fat[x][0].data = y;
      fat[x][0].Min = fat[x][0].N = edge[i];
      q.push(y);
    }
  }
}
int main() {
  long long n, m, i, j, k;
  scanf("%lld%lld", &n, &m);
  long long a[100010];
  t = (long long)(log(m) / log(2)) + 1;
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &j);
    add(i, a[i], j);
  }
  for (int i = 0; i < n; i++) fat[i][0].data = -1;
  for (int i = 0; i < n; i++)
    if (fat[i][0].data == -1) bfs(i);
  for (int j = 1; j <= t; j++)
    for (int i = 0; i < n; i++) {
      fat[i][j].data = fat[fat[i][j - 1].data][j - 1].data;
      fat[i][j].Min =
          min(fat[fat[i][j - 1].data][j - 1].Min, fat[i][j - 1].Min);
      fat[i][j].N = fat[i][j - 1].N + fat[fat[i][j - 1].data][j - 1].N;
    }
  for (int i = 0; i < n; i++) {
    long long temp = m, hh = i, ans = -1, h = 0;
    for (int j = t; j >= 0; j--) {
      if (pow(2, j) <= temp) {
        temp -= pow(2, j);
        h += fat[hh][j].N;
        if (ans != -1)
          ans = min(ans, fat[hh][j].Min);
        else
          ans = fat[hh][j].Min;
        hh = fat[hh][j].data;
      }
    }
    printf("%lld %lld\n", h, ans);
  }
}