Analysis of Pathes in Functional Graph

题意翻译

题目描述】 有一个n个点n条边的带权有向图（点编号0~n-1），每个点有且仅有一条出边，对于每个点i求出由i出发经过k条边，这k条边的权值最小值和权值和。 【输入格式】 第一行两个正整数n和k。 第二行n个正整数，第i个数表示i的出边指向的点。 第三行n个正整数，第i个数表示i的出边的权值。 【输出格式】 共n行，每行两个数，第一个数表示由点i出发经过k条边，这k条边的权值和，第二个数则表示权值的最小值。

题目描述

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} $ . 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.

输入输出格式

输入格式

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}&lt;n $ ) and the third — the sequence $ w_{0},w_{1},...,w_{n-1} $ ( $ 0<=w_{i}<=10^{8} $ ).

输出格式

Print $ n $ lines, the pair of integers $ s_{i} $ , $ m_{i} $ in each line.

输入输出样例

输入样例 #1

7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3

输出样例 #1

10 1
8 1
7 1
10 2
8 2
7 1
9 3

输入样例 #2

4 4
0 1 2 3
0 1 2 3

输出样例 #2

0 0
4 1
8 2
12 3

输入样例 #3

5 3
1 2 3 4 0
4 1 2 14 3

输出样例 #3

7 1
17 1
19 2
21 3
8 1