题目描述

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

数据规模与约定

对于所有数据，保证：

$2 \le n \le 100,000$

$1 \le k \le 10$

颜色是 $1$ 到 $2n$ 的一个排列

样例 1 解释：

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

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

子任务信息：

某些子任务满足 $k = 1$

某些子任务满足 $n \le 100$

某些子任务满足 $n \le 1,000$