CF702E.Analysis of Pathes in Functional Graph

You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.

Graph is given as the array _f_0, _f_1, ..., f__n - 1, where f__i — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs _w_0, _w_1, ..., w__n - 1, where w__i — the arc weight from i to f__i.

The graph from the first sample test.

Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers s__i and m__i, where:

• s__i — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i;
• m__i — the minimal weight from all arcs on the path with length k which starts from the vertex i.

The length of the path is the number of arcs on this path.

你被给定一个函数图（functional graph）。它是一个有向图，其中每个顶点恰好引出一条有向边。顶点编号为 $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$（路径长度），你需要对每个顶点 $i$ 计算两个数 $s_i$ 和 $m_i$，其中：

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

路径的长度定义为该路径所包含的边的数量。

The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence _f_0, _f_1, ..., f__n - 1 (0 ≤ f__i < n) and the third — the sequence _w_0, _w_1, ..., w__n - 1 (0 ≤ w__i ≤ 108).

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

Print n lines, the pair of integers s__i, m__i in each line.

输出 n 行，每行包含一对整数 s__i 和 m__i。