Bajtuś 在圣尼古拉斯节收到父母送的一块大画布，画布被划分为 $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$。
Bajtuś 拿到画布后，将 $2n$ 个正方形中的每一个都涂上了不同的颜色。为简化起见，颜色用 $1$ 到 $2n$ 之间的整数表示。
艺术评论家 Bajton Bity 决定亲自评估这件作品。他使用的方法如下： 选择一个颜色区间 $[\ell, r]$，然后只考虑涂有该区间内颜色的正方形。我们称该颜色区间的“好奇度”等于这些正方形所形成的连通区域的数量。如果存在一条由涂有区间 $[\ell, r]$ 内颜色的相邻正方形组成的路径，则称两个正方形处于同一个区域中。
Bajton Bity 对好奇度为 $v$ 的区间数量感兴趣，其中 $v \in \{1, 2, \dots, k\}$。你的任务是回答他的问题。
输入格式
第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 100\,000$，$1 \le k \le 10$)，分别表示画布的宽度和 Bajton Bity 感兴趣的最大好奇度。
第二行包含 $n$ 个整数，描述第一行正方形的颜色，按列号递增的顺序排列。
第三行包含 $n$ 个整数，描述第二行正方形的颜色，按相同的顺序排列。
第二行和第三行中的数字构成了 $1$ 到 $2n$ 的一个排列。
输出格式
在唯一的一行中输出 $k$ 个整数，即对 Bajton Bity 后续问题的回答。第 $v$ 个数字应为好奇度为 $v$ 的颜色区间数量。
样例
样例输入 1
3 2 1 5 3 4 2 6
样例输出 1
12 9
样例输入 2
5 3 1 3 5 7 9 2 6 4 8 10
样例输出 2
40 14 1
说明
第一个样例的解释：考虑颜色区间 $[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, 4]$ 的好奇度为 $1$。
子任务
- 在某些测试组中，满足条件 $k = 1$。
- 在某些测试组中，满足条件 $n \le 100$。
- 在某些测试组中，满足条件 $n \le 1\,000$。
对于上述每种情况，至少存在一个满足该条件的测试组。不同条件的测试组可能重叠或不重叠。