Analysis of Pathes in Functional Graph

- 题目描述 有一个 $n$ 个点 $n$ 条边的带权有向图（点编号 $0\sim n-1$），每个点有且仅有一条出边，对于每个点 $i$ 求出由 $i$ 出发走过 $k$ 条边，这 $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},\dots,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},\dots,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\le n \le10^{5},1\le k\le10^{10}) $. The second line contains the sequence $ f_{0},f_{1},\dots,f_{n-1}\ ( 0\le f_{i}<n )$ and the third — the sequence $ w_{0},w_{1},...,w_{n-1}\ ( 0\le w_{i}\le10^{8} )$.

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

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

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

4 4
0 1 2 3
0 1 2 3

0 0
4 1
8 2
12 3

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

7 1
17 1
19 2
21 3
8 1