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 double eps = 1e-9;
const double pi = 3.14159265358979323846264338327950288419716939937510;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int mod2 = 1000000006;
const long long infll = 0x3f3f3f3f3f3f3f3fLL;
const int dx[8] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};
template <typename T>
inline bool RD(T& v) {
  char c;
  bool n;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    if (c == EOF) return false;
  if (c == '-') {
    n = true;
    v = 0;
  } else {
    n = false;
    v = c - '0';
  }
  while (c = getchar(), c >= '0' && c <= '9') v = (v << 3) + (v << 1) + c - '0';
  if (n) v *= -1;
  return true;
}
template <typename T>
inline bool RD(T& a, T& b) {
  return RD(a) && RD(b);
}
template <typename T>
inline bool RD(T& a, T& b, T& c) {
  return RD(a, b) && RD(c);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d) {
  return RD(a, b, c) && RD(d);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e) {
  return RD(a, b, c, d) && RD(e);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f) {
  return RD(a, b, c, d, e) && RD(f);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g) {
  return RD(a, b, c, d, e, f) && RD(g);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h) {
  return RD(a, b, c, d, e, f, g) && RD(h);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i) {
  return RD(a, b, c, d, e, f, g, h) && RD(i);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j) {
  return RD(a, b, c, d, e, f, g, h, i) && RD(j);
}
inline int RD() {
  int v;
  RD(v);
  return v;
}
static char _BUF_[1 << 15], *_HEAD_ = _BUF_, *_TAIL_ = _BUF_;
inline static char getchar_buffered() {
  return _HEAD_ == _TAIL_ &&
                 (_TAIL_ = (_HEAD_ = _BUF_) + fread(_BUF_, 1, 1 << 15, stdin),
                  _HEAD_ == _TAIL_)
             ? EOF
             : *_HEAD_++;
}
template <typename T>
inline bool RDB(T& v) {
  char c;
  bool n;
  while (c = getchar_buffered(), c != '-' && (c < '0' || c > '9'))
    if (c == EOF) return false;
  if (c == '-') {
    n = true;
    v = 0;
  } else {
    n = false;
    v = c - '0';
  }
  while (c = getchar_buffered() - '0', c >= 0 && c <= 9)
    v = (v << 3) + (v << 1) + c;
  if (n) v *= -1;
  return true;
}
template <typename T>
inline bool RDB(T& a, T& b) {
  return RDB(a) && RDB(b);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c) {
  return RDB(a, b) && RDB(c);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d) {
  return RDB(a, b, c) && RDB(d);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e) {
  return RDB(a, b, c, d) && RDB(e);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f) {
  return RDB(a, b, c, d, e) && RDB(f);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g) {
  return RDB(a, b, c, d, e, f) && RDB(g);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h) {
  return RDB(a, b, c, d, e, f, g) && RDB(h);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i) {
  return RDB(a, b, c, d, e, f, g, h) && RDB(i);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j) {
  return RDB(a, b, c, d, e, f, g, h, i) && RDB(j);
}
inline int RDB() {
  int v;
  RDB(v);
  return v;
}
template <typename T>
inline void _WR(T a) {
  if (a < 0) {
    putchar('-');
    a *= -1;
  }
  T t = a / 10;
  if (t) _WR(t);
  putchar(a - (t << 1) - (t << 3) + '0');
}
template <typename T>
inline void WR_(const T& a) {
  _WR(a);
  putchar(' ');
}
template <typename T>
inline void WR(const T& a) {
  _WR(a);
  putchar('\n');
}
template <typename T>
inline void _WR(const T& a, const T& b) {
  WR_(a);
  _WR(b);
}
template <typename T>
inline void WR_(const T& a, const T& b) {
  WR_(a);
  WR_(b);
}
template <typename T>
inline void WR(const T& a, const T& b) {
  WR_(a);
  WR(b);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c) {
  WR_(a, b);
  _WR(c);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c) {
  WR_(a, b);
  WR_(c);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c) {
  WR_(a, b);
  WR(c);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  _WR(d);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  WR_(d);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  WR(d);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  _WR(e);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  WR_(e);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  WR(e);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f) {
  WR_(a, b, c, d, e);
  _WR(f);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f) {
  WR_(a, b, c, d, e);
  WR_(f);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f) {
  WR_(a, b, c, d, e);
  WR(f);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  _WR(g);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  WR_(g);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  WR(g);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  _WR(h);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  WR_(h);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  WR(h);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  _WR(i);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  WR_(i);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  WR(i);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  _WR(j);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  WR_(j);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  WR(j);
}
template <typename A>
inline istream& IN(A& a) {
  return std::cin >> a;
}
template <typename A, typename B>
inline istream& IN(A& a, B& b) {
  return std::cin >> a >> b;
}
template <typename A, typename B, typename C>
inline istream& IN(A& a, B& b, C& c) {
  return std::cin >> a >> b >> c;
}
template <typename A, typename B, typename C, typename D>
inline istream& IN(A& a, B& b, C& c, D& d) {
  return std::cin >> a >> b >> c >> d;
}
template <typename A, typename B, typename C, typename D, typename E>
inline istream& IN(A& a, B& b, C& c, D& d, E& e) {
  return std::cin >> a >> b >> c >> d >> e;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f) {
  return std::cin >> a >> b >> c >> d >> e >> f;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H, typename I>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h, I& i) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h >> i;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H, typename I, typename J>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h, I& i, J& j) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j;
}
inline std::ostream& OUT() { return std::cout << std::endl; }
template <typename T>
inline ostream& _OUT(const T& a) {
  return std::cout << a;
}
template <typename T>
inline ostream& OUT_(const T& a) {
  return std::cout << a << ' ';
}
template <typename T>
inline ostream& OUT(const T& a) {
  return std::cout << a << std::endl;
}
template <typename T, typename U>
inline ostream& _OUT(const T& a, const U& b) {
  return std::cout << a << " " << b;
}
template <typename T, typename U>
inline ostream& OUT_(const T& a, const U& b) {
  return std::cout << a << " " << b << " ";
}
template <typename T, typename U>
inline ostream& OUT(const T& a, const U& b) {
  return std::cout << a << " " << b << std::endl;
}
template <typename T, typename U, typename V>
inline ostream& _OUT(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return _OUT(c);
}
template <typename T, typename U, typename V>
inline ostream& OUT_(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return OUT_(c);
}
template <typename T, typename U, typename V>
inline ostream& OUT(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return OUT(c);
}
template <typename T, typename U, typename V, typename W>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return _OUT(d);
}
template <typename T, typename U, typename V, typename W>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return OUT_(d);
}
template <typename T, typename U, typename V, typename W>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return OUT(d);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d,
                     const X& e) {
  OUT_(a, b, c, d);
  return _OUT(e);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d,
                     const X& e) {
  OUT_(a, b, c, d);
  return OUT_(e);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d,
                    const X& e) {
  OUT_(a, b, c, d);
  return OUT(e);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f) {
  OUT_(a, b, c, d, e);
  return _OUT(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f) {
  OUT_(a, b, c, d, e);
  return OUT_(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f) {
  OUT_(a, b, c, d, e);
  return OUT(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return _OUT(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return OUT_(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return OUT(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return _OUT(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return OUT_(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return OUT(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return _OUT(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return OUT_(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return OUT(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i,
                     const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return _OUT(j);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i,
                     const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return OUT_(j);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h, const B& i,
                    const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return OUT(j);
}
template <typename A>
inline void clr(A& a) {
  a.clear();
}
template <typename A, typename B>
inline void clr(A& a, B& b) {
  a.clear();
  b.clear();
}
template <typename A, typename B, typename C>
inline void clr(A& a, B& b, C& c) {
  a.clear();
  b.clear();
  c.clear();
}
template <typename A, typename B, typename C, typename D>
inline void clr(A& a, B& b, C& c, D& d) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
}
template <typename A, typename B, typename C, typename D, typename E>
inline void clr(A& a, B& b, C& c, D& d, E& e) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
  e.clear();
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F>
inline void clr(A& a, B& b, C& c, D& d, E& e, F& f) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
  e.clear();
  f.clear();
}
inline long long madd(long long a, long long b,
                      const long long mod = 1000000007) {
  long long ret = (a + b) % mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline long long msub(long long a, long long b,
                      const long long mod = 1000000007) {
  long long ret = (a - b) % mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline long long mmul(long long a, long long b,
                      const long long mod = 1000000007) {
  return a * b % mod;
}
inline long long mpow(long long x, long long k,
                      const long long mod = 1000000007) {
  x %= mod;
  long long ret = 1;
  while (k > 0) {
    if (k & 1) ret = ret * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return ret;
}
template <typename T, typename U>
inline bool cmax(T& a, const U& b) {
  return a < b ? a = b, true : false;
}
template <typename T, typename U>
inline bool cmin(T& a, const U& b) {
  return a > b ? a = b, true : false;
}
template <typename T, typename U>
inline T cadd(T& a, const U& b, const int mod = 1000000007) {
  a = (a * 1LL + b) % mod;
  if (a < 0) a += mod;
  return a;
}
template <typename T, typename U>
inline T csub(T& a, const U& b, const int mod = 1000000007) {
  a = (a * 1LL - b) % mod;
  if (a < 0) a += mod;
  return a;
}
template <typename T, typename U>
inline T cmul(T& a, const U& b, const int mod = 1000000007) {
  return a = (a * 1LL * b) % mod;
}
inline long long cpow(long long& x, long long k,
                      const long long mod = 1000000007) {
  x %= mod;
  long long ret = 1;
  while (k > 0) {
    if (k & 1) ret = ret * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return x = ret;
}
template <typename T>
inline T clow(T& a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  return a;
}
template <typename T>
inline T cup(T& a, const int mod = 1000000007) {
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T cboth(T& a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T vlow(T a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  return a;
}
template <typename T>
inline T vup(T a, const int mod = 1000000007) {
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T vboth(T a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T max(const T& a, const T& b, const T& c) {
  return std::max(std::max(a, b), c);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d) {
  return std::max(max(a, b, c), d);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e) {
  return std::max(max(a, b, c, d), e);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f) {
  return std::max(max(a, b, c, d, e), f);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g) {
  return std::max(max(a, b, c, d, e, f), g);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h) {
  return std::max(max(a, b, c, d, e, f, g), h);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i) {
  return std::max(max(a, b, c, d, e, f, g, h), i);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i, const T& j) {
  return std::max(max(a, b, c, d, e, f, g, h, i), j);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c) {
  return std::min(std::min(a, b), c);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d) {
  return std::min(min(a, b, c), d);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e) {
  return std::min(min(a, b, c, d), e);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f) {
  return std::min(min(a, b, c, d, e), f);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g) {
  return std::min(min(a, b, c, d, e, f), g);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h) {
  return std::min(min(a, b, c, d, e, f, g), h);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i) {
  return std::min(min(a, b, c, d, e, f, g, h), i);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i, const T& j) {
  return std::min(min(a, b, c, d, e, f, g, h, i), j);
}
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) {
    T tmp = b;
    b = a % b;
    a = tmp;
  }
  return a;
}
template <typename T>
inline T egcd(T a, T b, T& x, T& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  T gcd = egcd(b, a % b, y, x);
  y -= (a / b) * x;
  return gcd;
}
template <typename T>
struct point {
  T x, y;
  point() {}
  point(T xx, T yy) : x(xx), y(yy) {}
  point(const point& B) : x(B.x), y(B.y) {}
  bool operator==(const point& B) const { return x == B.x && y == B.y; }
  bool operator!=(const point& B) const { return x != B.x || y != B.y; }
  bool operator<(const point& B) const {
    return x < B.x || x == B.x && y < B.y;
  }
  bool operator>(const point& B) const {
    return x > B.x || x == B.x && y > B.y;
  }
  bool operator<=(const point& B) const {
    return x < B.x || x == B.x && y <= B.y;
  }
  bool operator>=(const point& B) const {
    return x > B.x || x == B.x && y >= B.y;
  }
  point& operator=(const point& B) {
    x = B.x;
    y = B.y;
    return *this;
  }
  point operator+(const point& B) const { return point(x + B.x, y + B.y); }
  point operator-(const point& B) const { return point(x - B.x, y - B.y); }
  point& operator+=(const point& B) {
    x += B.x;
    y += B.y;
    return *this;
  }
  point& operator-=(const point& B) {
    x -= B.x;
    y -= B.y;
    return *this;
  }
  T operator*(const point& B) const { return x * B.x + y * B.y; }
  T operator^(const point& B) const { return x * B.y - y * B.x; }
};
const int _ = (int)(1e5 + 10);
const int __ = (int)(1e6 + 10);
const int LOG = 50;
int Log;
long long n, k;
int e[_], w[_];
long long ret_sum[_], ret_minw[_];
bool vis[_];
struct Status {
  int to[LOG];
  long long sumw[LOG];
  int minw[LOG];
} S[_];
void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  S[u].to[0] = e[u];
  S[u].sumw[0] = w[u];
  S[u].minw[0] = w[u];
  dfs(e[u]);
}
inline void _main() {
  RDB(n, k);
  {
    for (long long _i_ = (long long)(0); _i_ < (long long)(n); ++_i_)
      RDB((e)[_i_]);
  };
  {
    for (long long _i_ = (long long)(0); _i_ < (long long)(n); ++_i_)
      RDB((w)[_i_]);
  };
  while ((1LL << Log) <= k) ++Log;
  for (long long i = 0; i < (long long)(n); ++i) dfs(i);
  for (long long j = (long long)(1); j < (long long)(Log); ++j)
    for (long long i = 0; i < (long long)(n); ++i) {
      int mid = S[i].to[j - 1];
      S[i].to[j] = S[mid].to[j - 1];
      S[i].sumw[j] = S[i].sumw[j - 1] + S[mid].sumw[j - 1];
      S[i].minw[j] = min(S[i].minw[j - 1], S[mid].minw[j - 1]);
    }
  for (long long i = 0; i < (long long)(n); ++i) {
    ret_minw[i] = inf;
    long long d = k;
    int u = i;
    for (long long j = (long long)(Log)-1; j >= 0; --j)
      if ((d >> j) & 1) {
        ret_sum[i] += S[u].sumw[j];
        cmin(ret_minw[i], S[u].minw[j]);
        d -= 1LL << j;
        u = S[u].to[j];
      }
  }
  for (long long i = 0; i < (long long)(n); ++i) WR(ret_sum[i], ret_minw[i]);
}
void generate_test_case() { exit(0); }
int main() {
  _main();
  return 0;
}