您将获得一个函数图。它是一个有向图,其中每个顶点恰好经过一条弧。顶点从 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