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 PYTHON3):

Solution:
import sys
n, k = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
b = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))

logk = len(bin(k)) - 2
sum_w, sum_w_p = b[:], b[:]
min_w, min_w_p = b[:], b[:]
dest, dest_p = a[:], a[:]

ans_sum, ans_min, pos = [0]*n, b[:], list(range(n))
if k & 1:
    ans_sum = b[:]
    pos = [a[i] for i in range(n)]
k >>= 1

for j in range(1, logk):
    for i in range(n):
        d = dest[i]
        p = 0 if d > i else 1
        dest_p[i] = d
        dest[i] = (dest_p if p else dest)[d]
        sum_w_p[i] = sum_w[i]
        sum_w[i] += (sum_w_p if p else sum_w)[d]
        min_w_p[i] = min_w[i]
        if min_w[i] > (min_w_p if p else min_w)[d]:
            min_w[i] = (min_w_p if p else min_w)[d]

    if k & 1:
        for i in range(n):
            ans_sum[i] += sum_w[pos[i]]
            if ans_min[i] > min_w[pos[i]]:
                ans_min[i] = min_w[pos[i]]
            pos[i] = dest[pos[i]]
    k >>= 1


sys.stdout.buffer.write('\n'.join(
    (str(ans_sum[i]) + ' ' + str(ans_min[i]) for i in range(n))).encode('utf-8'))