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 int N = 100001;
const int sizeTree = 1 << 19;
const int INF = 1e9;
long long tMin[sizeTree], tSum[sizeTree];
int n;
long long k;
int f[N], w[N];
vector<int> topSort;
int used[N];
int num[N];
int length[N], numCycle[N], start[N], _end[N];
int cntCycle;
int size;
int p[N][20], mn[N][20];
long long sum[N][20];
long long getMin(int v, int tl, int tr, int l, int r) {
  if (l > r) return INF;
  if (tl == l && tr == r) return tMin[v];
  int tm = (tl + tr) / 2;
  return min(getMin(2 * v, tl, tm, l, min(r, tm)),
             getMin(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
long long getSum(int v, int tl, int tr, int l, int r) {
  if (l > r) return 0;
  if (tl == l && tr == r) return tSum[v];
  int tm = (tl + tr) / 2;
  return getSum(2 * v, tl, tm, l, min(r, tm)) +
         getSum(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}
void assign(int v, int tl, int tr, int pos, int value) {
  if (tl == tr) {
    tSum[v] = value;
    tMin[v] = value;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    assign(2 * v, tl, tm, pos, value);
  else
    assign(2 * v + 1, tm + 1, tr, pos, value);
  tSum[v] = tSum[2 * v] + tSum[2 * v + 1];
  tMin[v] = min(tMin[2 * v], tMin[2 * v + 1]);
}
void dfs(int v) {
  used[v] = 1;
  if (used[f[v]] == 1) {
    int s = v;
    start[cntCycle] = v;
    length[cntCycle] = 0;
    do {
      num[s] = size;
      assign(1, 0, n - 1, num[s], w[s]);
      numCycle[s] = cntCycle;
      length[cntCycle]++;
      s = f[s];
      size++;
    } while (s != v);
    cntCycle++;
  }
  if (used[f[v]] == 0) dfs(f[v]);
  used[v] = 2;
}
void up(int v) {
  used[v] = 1;
  if (used[f[v]] == 0 && numCycle[f[v]] == -1) up(f[v]);
  p[v][0] = f[v];
  sum[v][0] = w[v];
  mn[v][0] = w[v];
  for (int i = 1; i < 20; ++i) {
    if (p[v][i - 1] != -1) {
      p[v][i] = p[p[v][i - 1]][i - 1];
      mn[v][i] = min(mn[p[v][i - 1]][i - 1], mn[v][i - 1]);
      sum[v][i] = sum[p[v][i - 1]][i - 1] + sum[v][i - 1];
    } else {
      p[v][i] = -1;
      mn[v][i] = INF;
      sum[v][i] = 0;
    }
  }
}
pair<long long, long long> get2(int& v, long long& k) {
  pair<long long, int> ans(0, INF);
  for (int i = 19; i >= 0; --i) {
    if ((1 << i) <= k && p[v][i] != -1) {
      ans.first += sum[v][i];
      ans.second = min(ans.second, mn[v][i]);
      v = p[v][i];
      k -= (1 << i);
    }
  }
  return ans;
}
pair<long long, long long> get(int i, long long k) {
  long long sum = 0;
  long long mn = INF;
  int p = numCycle[i];
  int v = start[p];
  int tmpk = k;
  if (k > length[p]) {
    tmpk = k % length[p];
    sum = (k / length[p]) * getSum(1, 0, n - 1, num[v], num[v] + length[p] - 1);
    mn = getMin(1, 0, n - 1, num[v], num[v] + length[p] - 1);
  }
  if (num[i] + tmpk - 1 <= num[v] + length[p] - 1) {
    sum += getSum(1, 0, n - 1, num[i], num[i] + tmpk - 1);
    mn = min(mn, getMin(1, 0, n - 1, num[i], num[i] + tmpk - 1));
  } else {
    int l1 = num[i], r1 = num[v] + length[p] - 1;
    int l2 = num[v], r2 = num[v] + tmpk - (num[v] + length[p] - num[i]) - 1;
    sum += getSum(1, 0, n - 1, l1, r1);
    sum += getSum(1, 0, n - 1, l2, r2);
    mn = min(mn, getMin(1, 0, n - 1, l1, r1));
    mn = min(mn, getMin(1, 0, n - 1, l2, r2));
  }
  return make_pair(sum, mn);
}
int main() {
  memset(numCycle, -1, sizeof(numCycle));
  memset(p, -1, sizeof(p));
  for (int i = 0; i < 20; ++i) {
    for (int j = 0; j < N; ++j) mn[j][i] = INF;
  }
  scanf("%d%I64d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &f[i]);
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &w[i]);
  }
  size = 0;
  for (int i = 0; i < n; ++i) {
    if (used[i] == 0) dfs(i);
  }
  memset(used, 0, sizeof(used));
  for (int i = 0; i < n; ++i) {
    if (used[i] == 0 && numCycle[i] == -1) up(i);
  }
  for (int i = 0; i < n; ++i) {
    long long sum = 0;
    int mn = INF;
    if (numCycle[i] == -1) {
      long long tmpk = k;
      int v = i;
      pair<long long, int> a = get2(v, tmpk);
      if (tmpk > 0) {
        pair<long long, long long> b = get(v, tmpk);
        a.first += b.first;
        a.second = min((int)b.second, a.second);
      }
      sum = a.first;
      mn = a.second;
    } else {
      pair<long long, long long> a = get(i, k);
      sum = a.first;
      mn = a.second;
    }
    printf("%I64d %d\n", sum, mn);
  }
  return 0;
}