当前没有测试数据。

2.图上查询

题目描述

有一个$n$个点$n$条边的有向图，第$i$条边从$i-1$指向$f_i$，边权为$w_i$的边，对每个点求从它出发经过$k$条边，这$k$条边的权值和$s_i$以及这$k$条边的权值最小值$m_i$。

输入格式

第一行两个数$n$和$k$。

第二行$n$个数$f_i$。

第三行$n$个数$w_i$。

输出格式

每行两个数$s_i$和$m_i$。

数据范围与提示

• 对于$30\%$的数据：$n,k \leq 10^{3}$；
• 对于$100\%$的数据：$1 \leq n \leq 10^{5}$，$1 \leq k \leq 10^{10}$，$0 \leq f_i < n$，$1 \leq w_i \leq 10^{8}$。

样例

7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3

10 1
8 1
7 1
10 2
8 2
7 1
9 3