← 返回题目列表

Codeforces · 702/E

E. 函数图中的路径分析

中文机器翻译题面 查看原题

您将获得一个函数图。它是一个有向图,其中每个顶点恰好经过一条弧。顶点从 0 到 n - 1 编号。

图以数组 f0, f1, ..., fn - 1 的形式给出,其中 fi — 从顶点 i 出发的唯一弧所到达的顶点数。此外,还给出了包含弧 w0、w1、...、wn - 1 权重的数组,其中 wi — 从 i 到 fi 的弧权重。

第一个样本测试的图表。

此外,您还获得了整数 k(路径的长度),并且需要为每个顶点找到两个数字 si 和 mi,其中:

- si — 从顶点 i 开始的长度为 k 的路径的所有弧的权重之和;
- mi — 从顶点 i 开始、长度为 k 的路径上所有弧的最小权重。

路径的长度是该路径上的弧数。

输入

第一行包含两个整数 n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010)。第二行包含序列 f0, f1, ..., fn - 1 (0 ≤ fi < n),第三行包含序列 w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108)。

输出

打印 n 行,每行包含一对整数 si, mi。

示例

输入 #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