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;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
const long long INF = 1001001001;
long long N, K;
long long F[111111], W[111111];
long long nex[40][111111];
long long sum[40][111111];
long long mi[40][111111];
signed main() {
  scanf("%lld%lld", &N, &K);
  for (long long i = 0; i < (N); i++) scanf("%lld", &F[i]);
  for (long long i = 0; i < (N); i++) scanf("%lld", &W[i]);
  for (long long i = 0; i < (N); i++) {
    nex[0][i] = F[i];
    sum[0][i] = mi[0][i] = W[i];
  }
  for (long long k = 0; k + 1 < 40; k++) {
    for (long long i = 0; i < (N); i++) {
      sum[k + 1][i] = sum[k][i] + sum[k][nex[k][i]];
      mi[k + 1][i] = min(mi[k][i], mi[k][nex[k][i]]);
      nex[k + 1][i] = nex[k][nex[k][i]];
    }
  }
  for (long long i = 0; i < (N); i++) {
    long long pos = i, s = 0, m = INF;
    for (long long j = 0; j < (40); j++) {
      if (K >> j & 1) {
        s += sum[j][pos];
        chmin(m, mi[j][pos]);
        pos = nex[j][pos];
      }
    }
    printf("%lld %lld\n", s, m);
  }
  return 0;
}