题目描述

题目译自 PA 2022 Runda 4 Płótno

由于圣诞节，Bytie 从父母那里得到了一块大画布，画布被分成 $2n$ 个方格，排列成两行 $n$ 列的矩形。为了方便在上面画画，这块画布被包在在一个很低很宽的圆柱体的侧面上，这样，画布的第一列就与最后一列相邻。如果画布上的两个方格有一条公共边，则认为它们是相邻的。即它们要么在同一列，要么在同一行的相邻列。

数学上，我们可以用一个有序数对 $(y,x)$ 表示画布上的每个方格，其中 $1\le y\le 2,1\le x\le n$。两个方格 $(y_1,x_1)$ 和 $(y_2,x_2)$ 相邻，如果满足：

• 它们在同一行，即 $y_1=y_2$，并且列相邻，即 $x_1+1\equiv x_2 \pmod n$ 或 $x_2+1\equiv x_1\pmod n$，或者
• 它们在同一列，即 $x_1=x_2$。

Bytie 一到画布前，就把 $2n$ 个方格的每一个都画成了不同的颜色。为简单起见，我们用 $1$ 到 $2n$ 的整数来表示颜色。

每个看到这个孩子的劳动成果的人都对这么小的孩子能够创造出如此宏伟的作品而感到非常惊讶。这甚至吸引了著名的艺术评论家 Bytona Bitego。他决定亲眼看看是什么让人们如此着迷，他将用自己特别准备的方法评估他的画，其方法如下：

我们选择一个特定的颜色区间 $[l, r]$，然后只考虑颜色在这个区间内的方格。我们称这个颜色区间的好奇值等于这些方格形成的连通区域的数量。如果存在一连串颜色在 $[l, r]$ 中的相邻方格使得两个颜色在 $[l,r]$ 的方格连通，那么这两个方格就在一个区域内。

Bytona Bitego 想知道对于每个 $v\in \{1,2,\ldots,k\}$，有多少区间的好奇值为 $v$。你的任务就是回答他的问题。

输入格式

第一行包含两个整数 $n,k\ (2\le n\le 100\ 000,1\le k\le 10)$，分别表示画布的宽度和 Bajtona Bitego 想知道的最大好奇值。

第二行包含 $n$ 个整数，表示画布第一行方格的颜色。从左到右按列编号递增顺序给出。

类似地，第三行包含 $n$ 个整数，表示画布第二行方格的颜色，顺序与第一行相同。

第二行和第三行的数字合起来形成了一个 $1$ 到 $2n$ 的整数排列。

输出格式

输出一行 $k$ 个整数，第 $v$ 个整数表示有多少个区间的好奇值为 $v$。

3 2
1 5 3
4 2 6

12 9

5 3
1 3 5 7 9
2 6 4 8 10

40 14 1

数据范围与提示

• 某些子任务满足 $k=1$。
• 某些子任务满足 $n\le 100$。
• 某些子任务满足 $n\le 1\ 000$。

对于上面提到的每种情况，都存在至少一个子任务满足。这些子任务满足条件可能不相交，也可能相交。