题目描述

给定一张 $n$ 个点的有向图，每个点有且只有一个后继，第 $i$ 个点的后继编号为 $t_i$，从 $i$ 到 $t_i$ 的边权重为 $w_i$。

给定一个整数 $k$，依次从每个点出发，沿着图中给定的后继前进，经过 $k$ 条边后停止，请分别求出从每个点出发的路径上经过的最大权重。

输入格式

第一行：两个整数表示 $n$ 与 $k$； 第二行：$n$ 个整数表示 $t_1,t_2,\dots,t_n$； 第三行：$n$ 个整数表示 $w_1,w_2,\dots,w_n$。

输出格式

共 $n$ 行，其中第 $i$ 行表示从 $i$ 号点出发，经过 $k$ 条边后停止时，路径上的最大权重。

6 4
2 3 1 5 4 1
10 20 30 40 50 60

30
30
30
50
50
60

样例解释 1

123与45分别形成一个圈

数据范围

• 对于 $50\%$ 的数据，$1\leq n, k\leq 2000$，
• 对于 $100\%$ 的数据，$1\leq n, k\leq 500,000$，
• $1\leq w_i\leq 1,000,000,000$