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
1 1
0
10000
 2 3
1 0
4 7
 1 2
0
10000
 3 10
0 1 2
9240 5331 6721
 4 10
2 1 2 1
960 2596 3752 8303
 6 10
0 3 3 5 3 5
4845 6494 579 5025 2998 4787
 1 10000000000
0
10000
 2 3
0 1
4 7
 2 3
1 1
4 7
 8 10
7 5 0 0 2 3 6 3
2948 525 5789 4809 3961 6111 5209 8128
 2 3
0 0
4 7
 5 10
0 2 2 0 2
8473 9299 7399 4396 7275
 20 10
13 10 5 6 18 5 12 13 15 1 10 3 9 16 7 9 7 11 9 13
2634 7980 171 3503 6601 9378 4618 8243 9343 1979 4172 7441 9722 9863 6041 4790 1737 7586 6461 228
 7 10
4 6 4 6 4 2 0
5590 6764 2775 3854 4798 348 3954

                                                           10000                                                            10000
                                                               15                                                                4
                                                              18                                                                4
                                                            20000                                                            10000
                                                            92400                                                             9240
                                                           53310                                                             5331
                                                           67210                                                             6721
                                                            34728                                                              960
                                                           25960                                                             2596
                                                           37520                                                             3752
                                                           31667                                                             2596
                                                            48450                                                             4845
                                                           49815                                                             4787
                                                           43900                                                              579
                                                           48108                                                             4787
                                                           46319                                                             2998
                                                           47870                                                             4787
 100000000000000 10000
                                                               12                                                                4
                                                              21                                                                7
                                                               18                                                                4
                                                              21                                                                7
                                                            50603                                                             2948
                                                           46163                                                              525
                                                           53444                                                             2948
                                                           52464                                                             2948
                                                           52596                                                             2948
                                                           53766                                                             2948
                                                           52090                                                             5209
                                                           55783                                                             2948
                                                               12                                                                4
                                                              15                                                                4
                                                            84730                                                             8473
                                                           75890                                                             7399
                                                           73990                                                             7399
                                                           80653                                                             4396
                                                           73866                                                             7275
                                                            62163                                                             1737
                                                           45528                                                             4172
                                                           84573                                                              171
                                                           48662                                                             1979
                                                           48053                                                             1979
                                                           93780                                                             9378
                                                           49331                                                             1979
                                                           67772                                                             1737
                                                           49124                                                             1979
                                                           43335                                                             1979
                                                           41720                                                             4172
                                                           51931                                                             1979
                                                           48885                                                             1979
                                                           69392                                                             1737
                                                           65570                                                             1737
                                                           43953                                                             1979
                                                           61266                                                             1737
                                                           55345                                                             1979
                                                           45624                                                             1979
                                                           59757                                                              228
                                                            48772                                                             4798
                                                           49894                                                             3954
                                                           45957                                                             2775
                                                           46984                                                             3854
                                                           47980                                                             4798
                                                           41507                                                              348
                                                           47928                                                             3954

#include <bits/stdc++.h>
using namespace std;
const long long MX = 1e18;
const long long MD = 1e9 + 7;
const long long MXX = 1e6 + 6;
long long n, k, a[100005][40], mn[100005][40], wa[100005][40];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i][0];
  for (int i = 0; i < n; i++) {
    cin >> wa[i][0];
    mn[i][0] = wa[i][0];
  }
  for (int i = 1; i < 40; i++) {
    for (int j = 0; j < n; j++) {
      a[j][i] = a[a[j][i - 1]][i - 1];
      wa[j][i] = wa[j][i - 1] + wa[a[j][i - 1]][i - 1];
      mn[j][i] = min(mn[j][i - 1], mn[a[j][i - 1]][i - 1]);
    }
  }
  for (int j = 0; j < n; j++) {
    long long l = j, ans1 = 0, ans2 = 1e9;
    for (int i = 0; i <= 40; i++) {
      if ((1 << i) & k) {
        ans1 += wa[l][i];
        ans2 = min(ans2, mn[l][i]);
        l = a[l][i];
      }
    }
    cout << ans1 << ' ' << ans2 << endl;
  }
}
