题目描述

题目译自 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

我们考虑颜色区间 $[1,3]$，我们感兴趣的是画布上的 $(1,1),(1,3)$ 和 $(2,2)$ 位置。其中 $(1,1)$ 和 $(1,3)$ 是相邻的，所以它们形成了一个连通区域，另一方面，$(2,2)$ 不与其他方格相邻，所以它自己是一个连通区域。这种情况下我们有 $2$ 个区域，所以颜色区间 $[1,3]$ 的好奇值为 $2$。

让我们再考虑颜色区间 $[1,4]$，这是我们感兴趣的是画布上的 $(1,1),(1,3),(2,1)$ 和 $(2,2)$ 位置。对于这四个方格，可以从任意一个方格出发，仅经过这四个方格而到达这四个方格中的其他任意方格。因此它们形成了 $1$ 个区域，这样颜色区间 $[1,4]$ 的好奇值为 $1$。

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

40 14 1

数据范围与提示

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

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