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:
g = {}
def push(u, v, w):
    g[u] = [v, w]
 
n, pos  = map(int, input().split())
V = list(map(int, input().split()))
W = list(map(int, input().split()))
 
for _ in range(n):
    push(_, V[_], W[_])
 
max_log = 35
next_n  = [[-1] * n for _ in range(max_log)]
next_m  = [[float('inf')] * n for _ in range(max_log)]
next_s  = [[0] * n for _ in range(max_log)]
 
for u in range(n):
    v, w      = g[u]
    next_n[0][u]  = v
    next_m[0][u]  = w
    next_s[0][u]  = w
    
for k in range(1, max_log):
    for u in range(n):
        v  = next_n[k-1][u]
        m  = next_m[k-1][u]
        s  = next_s[k-1][u]
    
        next_n[k][u] = next_n[k-1][v] 
        next_m[k][u] = min(next_m[k-1][v], m)
        next_s[k][u] = next_s[k-1][v] + s
    
m_arr = [float('inf')] * n
s_arr = [0] * n
 
for _ in range(n):
    s, m = 0, float('inf')
    v    = _
    
    cur = 1<<max_log
    i   = max_log
 
    while cur > 0:
        if cur & pos:
            m = min(m, next_m[i][v])
            s = s + next_s[i][v]
            v = next_n[i][v]
            
        cur >>= 1
        i    -= 1
        
    m_arr[_] = m
    s_arr[_] = s
    
arr = [str(x) + ' ' + str(y) for x, y in zip(s_arr, m_arr)]
print('\n'.join([x for x in arr]))