Curiosity and the Canvas

Bytie has received a large canvas for Christmas. The canvas is divided into 2n square cells arranged in 2 rows and n columns. To facilitate painting, the canvas is wrapped around a very low and wide cylinder so that the first column is adjacent to the last column. Two cells are considered adjacent if they share a common edge. That is, either they are in the same column, or they are in the same row and in consecutive (cyclic) columns.

We identify every cell by an ordered pair \((y,x)\) with \(1 \le y \le 2\) and \(1 \le x \le n\). Two cells \((y_1,x_1)\) and \((y_2,x_2)\) are adjacent if either:

• They are in the same row \((y_1=y_2)\) and their columns are consecutive (modulo n), i.e. \(x_1+1 \equiv x_2 \; (\bmod\; n)\) or \(x_2+1 \equiv x_1 \; (\bmod\; n)\).
• They are in the same column \((x_1=x_2)\).

Before Bytie began painting, he painted every one of the 2n cells in a different color (represented by the integers from 1 to 2n). When people see his work, they are astonished that such a young child could create such a magnificent piece. The famous art critic Bytona Bitego has devised a special method for evaluating the painting:

For a fixed color interval \([l, r]\), consider only the cells whose colors belong to that interval. The curiosity of the interval is defined as the number of connected components formed by these cells (two cells are in the same component if there is a sequence of adjacent cells connecting them, all of which have colors within \([l,r]\)).

Bytona Bitego wonders, for each \(v \in \{1,2,\ldots,k\}\), how many color intervals \([l, r]\) (with \(1 \le l \le r \le 2n\)) have a curiosity value equal to \(v\). Your task is to answer his query.

inputFormat

The first line contains two integers \(n\) and \(k\). (Constraints are not explicitly specified.)

The next two lines each contain \(n\) integers. The first line gives the colors in the first row and the second line gives the colors in the second row of the canvas. The colors form a permutation of the integers from 1 to 2n.

outputFormat

Output \(k\) integers in a single line separated by a space. The \(v\)th integer should be the number of intervals \([l,r]\) (with \(1 \le l \le r \le 2n\)) whose curiosity (number of connected components) is equal to \(v\), for each \(v=1,2,\ldots,k\).

sample

2 3
1 4
2 3

1 2 0