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 f_0, f_1, ..., f_{n} - 1, where f_{i} — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w_0, w_1, ..., w_{n} - 1, where w_{i} — the arc weight from i to f_{i}. [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 s_{i} and m_{i}, where:  s_{i} — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i;  m_{i} — 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 ≤ 10^5, 1 ≤ k ≤ 10^10). The second line contains the sequence f_0, f_1, ..., f_{n} - 1 (0 ≤ f_{i} < n) and the third — the sequence w_0, w_1, ..., w_{n} - 1 (0 ≤ w_{i} ≤ 10^8).


-----Output-----

Print n lines, the pair of integers s_{i}, m_{i} 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

Difficulty: HARD
Tags: Graph algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
g = {}

def push(u, v, w):
	g[u] = [v, w]
(n, pos) = list(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]))


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'))