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;
template <class T>
void read(T& num) {
  char CH;
  bool F = false;
  for (CH = getchar(); CH < '0' || CH > '9'; F = CH == '-', CH = getchar())
    ;
  for (num = 0; CH >= '0' && CH <= '9';
       num = num * 10 + CH - '0', CH = getchar())
    ;
  F && (num = -num);
}
int stk[70], tp;
template <class T>
inline void print(T p) {
  if (!p) {
    puts("0");
    return;
  }
  tp = 0;
  while (p) stk[++tp] = p % 10, p /= 10;
  while (tp) putchar(stk[tp--] + '0');
  putchar('\n');
}
const int maxn = 200005, maxm = 400005;
int g[maxn], v[maxm], nxt[maxm], eid;
int siz[maxn], son[maxn], top[maxn], f[maxn];
int st[maxn], ed[maxn], vid;
int n, m, x;
char op[10];
void add(int a, int b) {
  v[eid] = b;
  nxt[eid] = g[a];
  g[a] = eid++;
}
struct Segtree {
  int sumv[maxm], sam[maxm], l[maxm], r[maxm];
  void update(int x) { sumv[x] = sumv[((x) << 1)] + sumv[(((x) << 1) | 1)]; }
  void push(int x) {
    if (sam[x] == -1) return;
    sam[((x) << 1)] = sam[x];
    sumv[((x) << 1)] = sam[x] * (r[((x) << 1)] - l[((x) << 1)] + 1);
    sam[(((x) << 1) | 1)] = sam[x];
    sumv[(((x) << 1) | 1)] =
        sam[x] * (r[(((x) << 1) | 1)] - l[(((x) << 1) | 1)] + 1);
    sam[x] = -1;
  }
  void change(int x, int L, int R, int val) {
    if (R < l[x] || L > r[x]) return;
    if (L <= l[x] && r[x] <= R) {
      sam[x] = val;
      sumv[x] = (r[x] - l[x] + 1) * val;
      return;
    }
    push(x);
    change(((x) << 1), L, R, val);
    change((((x) << 1) | 1), L, R, val);
    update(x);
  }
  int query(int x, int L, int R) {
    if (R < l[x] || L > r[x]) return 0;
    if (L <= l[x] && r[x] <= R) return sumv[x];
    push(x);
    return (query(((x) << 1), L, R) + query((((x) << 1) | 1), L, R));
  }
  void build(int x, int L, int R) {
    l[x] = L;
    r[x] = R;
    sam[x] = -1;
    if (L == R) return;
    int mid = L + R >> 1;
    build(((x) << 1), L, mid);
    build((((x) << 1) | 1), mid + 1, R);
  }
} seg;
void dfs(int u) {
  siz[u] = 1;
  for (int i = g[u]; ~i; i = nxt[i]) {
    dfs(v[i]);
    siz[u] += siz[v[i]];
    if (siz[v[i]] > siz[son[u]]) son[u] = v[i];
  }
}
void dfs2(int u, int rt) {
  top[u] = rt;
  st[u] = ++vid;
  if (son[u]) dfs2(son[u], rt);
  for (int i = g[u]; ~i; i = nxt[i])
    if (v[i] != son[u]) dfs2(v[i], v[i]);
  ed[u] = vid;
}
void solve(int x) {
  int ans = 0;
  while (x) {
    ans += (st[x] - st[top[x]] + 1) - seg.query(1, st[top[x]], st[x]);
    seg.change(1, st[top[x]], st[x], 1);
    x = top[x];
    x = f[x];
  }
  print(ans);
}
int fa[100005][40], w[100005], gmin[100005][40];
long long gsum[100005][40], k;
int main() {
  read(n);
  read(k);
  for (int i = 0; i < n; ++i) read(fa[i][0]);
  for (int i = 0; i < n; ++i) read(w[i]), gsum[i][0] = gmin[i][0] = w[i];
  for (int j = 1; j < 40; ++j)
    for (int i = 0; i < n; ++i) {
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
      gsum[i][j] = gsum[i][j - 1] + gsum[fa[i][j - 1]][j - 1];
      gmin[i][j] = min(gmin[i][j - 1], gmin[fa[i][j - 1]][j - 1]);
    }
  for (int i = 0; i < n; ++i) {
    int x = i, mn = 0x7fffffff;
    long long sum = 0;
    for (int j = 0; j < 40; ++j)
      if (k & (1LL << j)) {
        sum += gsum[x][j];
        mn = min(mn, gmin[x][j]);
        x = fa[x][j];
      }
    print(sum);
    print(mn);
  }
  return 0;
}