캔버스

Bajtuś는 니콜라우스 날에 부모님께 커다란 캔버스를 받았다. 캔버스는 2행 n열의 직사각형으로 배열된 2n개의 칸으로 나뉘어 있다. 캔버스를 다루기 쉽도록 매우 낮고 넓은 원기둥의 옆면에 씌워 두었기 때문에 첫 번째 열은 마지막 열과 이웃한다.

각 칸은 $(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까지의 정수로 나타낸다.

평론가 Bajtón Bitий는 다음 방법으로 이 작품을 평가한다. 색 구간 $[\ell, r]$을 골라, 색이 이 구간에 속하는 칸만 남긴다. 구간의 흥미도는 남은 칸들이 이루는 연결된 영역의 수이다. 두 칸은 남은 칸들을 따라 이웃하며 이어진 경로가 있으면 같은 영역에 속한다.

Bajtón Bitий는 $v \in \{1, 2, \ldots, k\}$마다 흥미도가 $v$인 색 구간이 몇 개인지 알고 싶어 한다.

첫 번째 줄에 캔버스의 너비 $n$과 Bajtón Bitий가 관심을 갖는 최대 흥미도 $k$가 주어진다 ($2 \le n \le 100\,000$, $1 \le k \le 10$).

두 번째 줄에는 첫 번째 행 칸들의 색 $n$개가 열 번호 오름차순으로 주어진다.

세 번째 줄에는 두 번째 행 칸들의 색 $n$개가 같은 순서로 주어진다.

두 번째 줄과 세 번째 줄의 수는 1부터 2n까지의 순열을 이룬다.

한 줄에 $k$개의 정수를 출력한다. $v$번째 정수는 흥미도가 $v$인 색 구간의 개수이다.

색 구간 $[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이다.