跳蚤国计算机协会 UOI 主席 “王中王” 认为 UOI 决赛不具有观赏性。

比如蟋蟀国的比赛，选手都需要在初赛快速 AK 才能晋级决赛，但 UOI 决赛只需要通过不到一半的题目就可以获得三十二强。

但是经过 UOI 系列委员会的商讨，比赛难度并没有被下调，因此王中王决定黑幕一些比赛结果。

具体来说，UOI 决赛总 $n$ 天，有 $m$ 名选手参加。现在王中王通过第六感得知，如果不加干预第 $i$ 天的比赛，那么第 $a_i$ 位选手将会胜出，但王中王每天可以将当天题目提前透露给任意一名选手。如果王中王透露了第 $i$ 天的题目，获得题目的选手将会成为那天比赛的胜利者，但他认为这样做比赛的合理性会降低 $w_i$。

不妨假设黑幕后每天的胜者依次为 $b_1, b_2, \dots, b_n$。王中王相信观众更喜欢看到“绝对强者”之间的对决，因此他认为一段赛程 $[l, r]$ 是“好看”的，当且仅当在该段赛程中，成为过胜者的选手数不超过二，即 $|\{b_l, b_{l+1}, \dots, b_r\}| \leq 2$。

而每一段“好看”的赛程，王中王认为都会让比赛的合理性增加 $1$。

而由于 UOI 决赛随时面临着缺投倒闭的风险，因此王中王想知道对于所有 $k = 1, 2, \dots, n$，如果 UOI 决赛只举办前 $k$ 天的比赛，比赛的合理性最高能是多少？

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

第三行 $n$ 个非负整数 $w_1, w_2, \dots, w_n$。

输出格式

一行 $n$ 个数，表示每个前缀的答案。

9 9
9 9 8 2 4 4 3 5 3
2 3 3 1 1 4 5 1 4

1 3 6 9 13 17 22 27 35

8 8
6 7 1 8 7 8 3 7
5 5 7 1 5 6 3 7

1 3 5 7 11 14 16 22

样例三 $\sim$ 九

见“附件下载”。

数据范围

$1 \leq n \leq 1500, 1 \leq a_i \leq m\leq 50, 0 \leq w_i \leq 10^6$

时间限制：$8\texttt{s}$

空间限制：$4\texttt{GB}$