问题描述

顿顿在剩余的 $n$ 天内准备完成 $m$ 项训练。第 $i$ 项训练编号为 $i$，耗时为 $t_i$ 天：若从第 $s$ 天开始训练，则该项训练的最后一天为 $s+t_i-1$。

每项训练最多只依赖一项其它训练，若科目 $i$ 依赖科目 $p_i$（且 $p_i<i$），则科目 $i$ 必须在科目 $p_i$ 训练结束后才能开始：若科目 $p_i$ 从第 $a$ 天开始训练并于第 $a+t_{p_i}-1$ 天结束，那么科目 $i$ 最早只能从第 $a+t_{p_i}$ 天开始训练。

没有依赖（即 $p_i=0$）的科目可以从第 $1$ 天开始训练。

请你计算每项科目的：

• 最早开始时间（最早能从哪一天开始训练）；
• 若能在第 $n$ 天前完成所有训练，则还需计算每项科目的最晚开始时间（在不耽误全部训练完成的前提下该科目能最晚从哪一天开始训练）。 若无法在第 $n$ 天内完成全部训练，则只需输出“最早开始时间”一行。

输入格式

共三行：

第一行：两个正整数 $n$ 和 $m$，分别表示可用天数和训练项数。

第二行：$m$ 个整数 $p_1,p_2,\dots,p_m$，其中 $0\le p_i<i$，若 $p_i=0$ 则科目 $i$ 无依赖。

第三行：$m$ 个正整数 $t_1,t_2,\dots,t_m$，其中 $1\le t_i\le n$。

• $0<n\le 365$，$0<m\le 100$。

输出格式

若计算最早开始时间为 $E_1,E_2,\dots,E_m$，最晚开始时间为 $L_1,L_2,\dots,L_m$：

• 若无法在第 $n$ 天内完成所有训练，仅输出一行：$E_1\;E_2\;\dots\;E_m$。
• 若可以完成，先输出第一行 $E_1\;E_2\;\dots\;E_m$，再输出第二行 $L_1\;L_2\;\dots\;L_m$。

各数之间用单个空格分隔。

输入样例 1

10 5
0 0 0 0 0
1 2 3 2 10

输出样例 1

1 1 1 1 1
10 9 8 9 1

输入样例 2

10 7
0 1 0 3 2 3 0
2 1 6 3 10 4 3

输出样例 2

1 3 1 7 4 7 1

输入样例 3

10 5
0 1 2 3 4
10 10 10 10 10

输出样例 3

1 11 21 31 41

说明

样例 1 解释

五项科目间没有依赖关系，都可以从第 $1$ 天就开始训练。

$10$ 天时间恰好可以完成所有科目的训练。

其中科目 $1$ 耗时仅 $1$ 天，所以最晚可以拖延到第 $10$ 天再开始训练；而科目 $5$ 耗时 $10$ 天，必须从第 $1$ 天就开始训练。

样例 2 解释

七项科目间的依赖关系如图所示，其中仅科目 $5$ 无法在 $10$ 天内完成训练。

具体来说，科目 $5$ 依赖科目 $2$ 、科目 $2$ 又依赖于科目 $1$，因此科目 $5$ 最早可以从第 $4$ 天开始训练。