Bajtuś received a large canvas from his parents for St. Nicholas Day, which was divided into $2n$ squares arranged in a rectangle consisting of two rows and $n$ columns. To make working with it easier, the canvas was wrapped around a very low and very wide cylinder, such that the first column of the canvas was adjacent to the last one. Two squares on the canvas are considered adjacent if they share a common side, meaning they are either in the same column, or in the same row and adjacent columns.
Mathematically, each square on the canvas can be denoted by a pair of numbers $(y, x)$, where $1 \le y \le 2$ and $1 \le x \le n$. Two squares $(y_1, x_1)$ and $(y_2, x_2)$ are adjacent if: they are in the same row, i.e., $y_1 = y_2$, and in adjacent columns, i.e., $x_1 + 1 \equiv x_2 \pmod n$ or $x_2 + 1 \equiv x_1 \pmod n$, or they are in the same column, i.e., $x_1 = x_2$.
As soon as Bajtuś got his hands on the canvas, he painted each of the $2n$ squares a different color. For simplicity, we will denote the colors with integers from $1$ to $2n$.
Everyone who saw the fruit of the toddler's work was deeply impressed that such a small child was able to create such a magnificent piece of art. This even attracted the famous art critic, Bajton Bity. He decided to see for himself what was so fascinating to people, so he evaluated this work using a method he prepared himself, which works as follows:
We choose a certain range of colors $[\ell, r]$, and then consider only the squares painted with colors from this range. We say that the curiosity of this color range is equal to the number of connected regions that these squares form. Two squares are in the same region if there exists a sequence of adjacent squares painted with colors from the range $[\ell, r]$ that connects them.
Bajton Bity is interested in how many ranges have a curiosity equal to $v$ for each $v \in \{1, 2, \dots, k\}$. Your task is to answer his questions.
Input
The first line of standard input contains two integers $n$ and $k$ ($2 \le n \le 100\,000$, $1 \le k \le 10$), representing the width of the canvas and the maximum curiosity Bajton Bity is interested in, respectively.
The second line contains $n$ integers describing the colors with which the squares of the first row of the canvas were painted, in order of increasing column numbers.
Similarly, the third line contains $n$ integers describing the colors with which the squares of the second row of the canvas were painted, in the same order.
The numbers in the second and third lines form a permutation of numbers from $1$ to $2n$.
Output
The only line of standard output should contain $k$ integers – the answers to Bajton Bity's subsequent questions. The $v$-th number should be the number of color ranges with curiosity $v$.
Examples
Input 1
3 2 1 5 3 4 2 6
Output 1
12 9
Input 2
5 3 1 3 5 7 9 2 6 4 8 10
Output 2
40 14 1
Note
Explanation of the first example: Consider the color range $[1, 3]$. We are interested in squares $(1, 1)$, $(1, 3)$, and $(2, 2)$ on the canvas. We can notice that squares $(1, 1)$ and $(1, 3)$ are adjacent to each other, so they form one region. On the other hand, square $(2, 2)$ is not adjacent to any other, so it forms its own separate region. We have 2 regions, so the curiosity of the range $[1, 3]$ is 2.
Consider also the range $[1, 4]$. We are interested in squares $(1, 1)$, $(1, 3)$, $(2, 1)$, and $(2, 2)$. Between any two squares with colors from this range, it is possible to move by walking only on other squares from this range. They therefore form one region, and the curiosity of the range $[1, 4]$ is 1.
Subtasks
- In some test groups, the condition $k = 1$ holds.
- In some test groups, the condition $n \le 100$ holds.
- In some test groups, the condition $n \le 1\,000$ holds.
For each of the above cases, there is at least one group that satisfies it. These groups may or may not be disjoint for different conditions.