函数图路径分析

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有一个包含 $n$ 个点和 $n$ 条带权有向边的图，点编号为 $0$ 到 $n-1$。每个点恰好有一条出边。

对于每个起点 $i$，从 $i$ 出发沿出边恰好走过 $k$ 条边。求这 $k$ 条边权值的总和与最小值。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $f_0,f_1,\ldots,f_{n-1}$，其中 $f_i$ 表示点 $i$ 的出边指向点 $f_i$。

第三行包含 $n$ 个整数 $w_0,w_1,\ldots,w_{n-1}$，其中 $w_i$ 表示点 $i$ 的出边权值。

输出格式

输出 $n$ 行。第 $i$ 行包含两个整数，依次表示从点 $i-1$ 出发走过 $k$ 条边后的边权总和与最小边权。

样例输入 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

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le k\le 10^{10}$，$0\le f_i<n$，$0\le w_i\le 10^8$。