markdown

E. 函数图中的路径分析

时间限制：每个测试点 $2$ 秒
内存限制：每个测试点 $512$ MB
输入：标准输入
输出：标准输出

给定一个函数图。这是一个有向图，其中每个顶点恰好有一条出边。顶点编号为 $0$ 到 $n-1$。

该图由数组 $f_0, f_1, \dots, f_{n-1}$ 给出，其中 $f_i$ 表示从顶点 $i$ 出发的唯一一条弧所指向的顶点编号。此外，还给出了弧的权重数组 $w_0, w_1, \dots, w_{n-1}$，其中 $w_i$ 表示从 $i$ 到 $f_i$ 的弧的权重。

（第一个样例测试对应的图）

同时给定一个整数 $k$（路径长度），你需要为每个顶点求出两个数 $s_i$ 和 $m_i$，其中：

• $s_i$ —— 从顶点 $i$ 出发、长度为 $k$ 的路径上所有弧的权重之和；
• $m_i$ —— 从顶点 $i$ 出发、长度为 $k$ 的路径上所有弧的最小权重。

路径长度指路径上弧的条数。

输入

第一行包含两个整数 $n, k$（$1 \le n \le 10^5$，$1 \le k \le 10^{10}$）。
第二行包含序列 $f_0, f_1, \dots, f_{n-1}$（$0 \le f_i < n$）。
第三行包含序列 $w_0, w_1, \dots, w_{n-1}$（$0 \le w_i \le 10^8$）。

输出

输出 $n$ 行，每行包含两个整数 $s_i, m_i$。

样例

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