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;
vector<long long> seg[2];
vector<int> ring_weight, ring_id;
void init(int n) {
  for (int i = 0; i < int(2); i++) {
    seg[i].resize(4 * n + 3);
  }
}
void make(int node, int u, int v) {
  if (u == v) {
    seg[0][node] = seg[1][node] = ring_weight[u];
    return;
  }
  int ls = (node << 1) | 1, rs = ls + 1, m = (u + v) >> 1;
  make(ls, u, m);
  make(rs, m + 1, v);
  seg[0][node] = seg[0][ls] + seg[0][rs];
  seg[1][node] = min(seg[1][ls], seg[1][rs]);
}
tuple<long long, int> read(int node, int u, int v, int first, int second) {
  if (first > v || second < u) {
    return make_pair(0, 1 << 30);
  }
  if (first <= u && v <= second) {
    return make_pair(seg[0][node], seg[1][node]);
  }
  int ls = (node << 1) | 1, rs = ls + 1, m = (u + v) >> 1;
  long long lx, rx;
  int ly, ry;
  tie(lx, ly) = read(ls, u, m, first, second);
  tie(rx, ry) = read(rs, m + 1, v, first, second);
  return make_pair(lx + rx, min(ly, ry));
}
vector<int> seen;
vector<int> ring_nodes;
vector<int> f, w;
vector<vector<int> > r, g;
int dfs(int u, int c) {
  seen[u] = c;
  if (seen[f[u]] == c) {
    ring_id[u] = int((ring_nodes).size());
    ring_nodes.push_back(u);
    return (u == f[u] ? -1 : f[u]);
  }
  if (seen[f[u]] != -1) {
    return -1;
  }
  int t = dfs(f[u], c);
  if (t != -1) {
    ring_id[u] = int((ring_nodes).size());
    ring_nodes.push_back(u);
  }
  return (t == u ? -1 : t);
}
vector<tuple<long long, int> > ans;
vector<int> M, D;
vector<long long> W;
tuple<long long, int> get_ans(int id, long long h) {
  long long first = 0;
  int second = 1 << 30;
  if (h >= int((ring_nodes).size())) {
    first = h / int((ring_nodes).size()) * seg[0][0];
    second = seg[1][0];
  }
  h %= int((ring_nodes).size());
  if (h <= 0) {
    return make_pair(first, second);
  }
  int jd = (id + h - 1 + int((ring_nodes).size())) % int((ring_nodes).size());
  if (jd < id) {
    long long tx;
    int ty;
    tie(tx, ty) = read(0, 0, int((ring_nodes).size()) - 1, id,
                       int((ring_nodes).size()) - 1);
    first += tx;
    second = min(second, ty);
    tie(tx, ty) = read(0, 0, int((ring_nodes).size()) - 1, 0, jd);
    first += tx;
    second = min(second, ty);
  } else {
    long long tx;
    int ty;
    tie(tx, ty) = read(0, 0, int((ring_nodes).size()) - 1, id, jd);
    first += tx;
    second = min(second, ty);
  }
  return make_pair(first, second);
}
long long k;
vector<int> Q, to;
long long dp[3][20][100005];
void bfs() {
  int fr = 0, bk = 0;
  for (int i = 0; i < int(int((ring_nodes).size())); i++) {
    M[ring_nodes[i]] = 1 << 30;
    W[ring_nodes[i]] = 0;
    D[ring_nodes[i]] = 0;
    Q[bk++] = ring_nodes[i];
    while (fr < bk) {
      int u = Q[fr++];
      if (D[u] < k) {
        long long first;
        int second;
        tie(first, second) = get_ans(i, k - D[u]);
        first += W[u];
        second = min(second, M[u]);
        ans[u] = make_pair(first, second);
      } else {
        to.push_back(u);
      }
      for (int j = 0; j < int(int((r[u]).size())); j++) {
        int v = r[u][j];
        if (ring_id[v] != -1) {
          continue;
        }
        D[v] = D[u] + 1;
        W[v] = W[u] + g[u][j];
        M[v] = min(M[u], g[u][j]);
        Q[bk++] = v;
        dp[0][0][v] = u;
        dp[1][0][v] = g[u][j];
        dp[2][0][v] = g[u][j];
      }
    }
  }
}
void solve(int u) {
  ring_nodes.clear();
  dfs(u, u);
  if (int((ring_nodes).size()) == 0) {
    return;
  }
  reverse((ring_nodes).begin(), (ring_nodes).end());
  ring_weight.clear();
  for (auto e : (ring_nodes)) {
    ring_weight.push_back(w[e]);
  }
  init(int((ring_nodes).size()));
  make(0, 0, int((ring_nodes).size()) - 1);
  bfs();
}
tuple<long long, int> get(int u, int k, int l) {
  long long first = 0;
  int second = 1 << 30;
  for (int i = l; i >= 0; i--) {
    if (dp[0][i][u] == -1 || k < (1 << i)) {
      continue;
    }
    first += dp[1][i][u];
    second = min(dp[2][i][u], 1ll * second);
    u = dp[0][i][u];
    k -= 1 << i;
  }
  return make_pair(first, second);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int n;
  cin >> n >> k;
  seen.resize(n, -1);
  f.resize(n);
  w.resize(n);
  r.resize(n);
  g.resize(n);
  M.resize(n);
  W.resize(n);
  D.resize(n);
  Q.resize(n);
  ans.resize(n);
  ring_id.resize(n, -1);
  for (int i = 0; i < int(n); i++) {
    cin >> f[i];
  }
  for (int i = 0; i < int(n); i++) {
    cin >> w[i];
  }
  for (int i = 0; i < int(n); i++) {
    r[f[i]].push_back(i);
    g[f[i]].push_back(w[i]);
  }
  memset(dp, -1, sizeof(dp));
  for (int i = 0; i < int(n); i++) {
    if (seen[i] == -1) {
      solve(i);
    }
  }
  if (int((to).size())) {
    for (int i = 1; (1 << i) <= n; i++) {
      for (int j = 0; j < int(n); j++) {
        int t = dp[0][i - 1][j];
        if (t != -1) {
          dp[0][i][j] = dp[0][i - 1][t];
          dp[1][i][j] = dp[1][i - 1][j] + dp[1][i - 1][t];
          dp[2][i][j] = min(dp[2][i - 1][j], dp[2][i - 1][t]);
        }
      }
    }
    int l = 31 - __builtin_clz(k);
    for (auto e : (to)) {
      ans[e] = get(e, k, l);
    }
  }
  for (auto a : (ans)) {
    long long first;
    int second;
    tie(first, second) = a;
    cout << first << " " << second << "\n";
  }
  return 0;
}