题目描述

有一个$n$个点$n$条边的带权有向图（点编号$0\sim n-1$），每个点有且仅有一条出边，对于每个点$i$求出由$i$出发经过$k$条边，这$k$条边的权值最小值和权值和。

样例1图解：

输入格式

第一行两个正整数$n$和$k$。

第二行$n$个正整数，第$i$个数表示$i$的出边指向的点。

第三行$n$个正整数，第$i$个数表示$i$的出边的权值。

输出格式

共$n$行，每行两个数，第一个数表示由点$i$出发经过$k$条边，这$k$条边的权值和，第二个数则表示权值的最小值。

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

数据范围

对于$100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq k\leq 10^{9}$，

$1\leq w_i\leq 10^8$