참고: 이 문제에서 만점을 받으려면 Python이 아닌 다른 언어를 사용하는 것을 권장한다.

농부 존의 소 \(N\)마리가 한 줄로 서 있다. 줄의 맨 앞에는 \(1\)번 소가 있고, 맨 뒤에는 \(N\)번 소가 있다. (\(1\le N\le 7500\)) 농부 존의 소들은 여러 종으로 나뉘며, 각 종은 \(1\)부터 \(N\)까지의 정수로 나타낸다. 줄의 앞에서 \(i\)번째에 있는 소의 종은 \(a_i\)이다. (\(1\le a_i\le N\))

농부 존은 소들을 지역 소 병원에 데려가 검진을 받게 하려고 한다. 하지만 수의사는 매우 까다로워서, 줄의 \(i\)번째 소가 종 \(b_i\)일 때에만 그 소를 검진한다. (\(1\le b_i\le N\))

농부 존은 게으르기 때문에 소들의 순서를 완전히 바꾸고 싶지는 않다. 대신 다음 연산을 정확히 한 번 수행한다.

• \(1\le l\le r\le N\)을 만족하는 두 정수 \(l\)과 \(r\)을 고른다. 줄에서 \(l\)번째 소부터 \(r\)번째 소까지의 순서를 뒤집는다.

농부 존은 이 방법이 얼마나 효과적인지 알고 싶다. 각 \(c=0,1,\ldots,N\)에 대해, 정확히 \(c\)마리의 소가 검진을 받게 하는 서로 다른 연산 \((l,r)\)의 수를 구하여라. 두 연산 \((l_1,r_1)\)과 \((l_2,r_2)\)는 \(l_1\ne l_2\)이거나 \(r_1\ne r_2\)이면 서로 다르다.

입력

첫째 줄에 정수 \(N\)이 주어진다.

둘째 줄에 \(a_1,a_2,\ldots,a_N\)이 공백으로 구분되어 주어진다.

셋째 줄에 \(b_1,b_2,\ldots,b_N\)이 공백으로 구분되어 주어진다.

출력

\(N+1\)개의 줄을 출력한다. \(i\)번째 줄에는 정확히 \(i-1\)마리의 소가 검진을 받게 하는 서로 다른 연산 \((l,r)\)의 수를 출력한다.

예제 입력 1

3
1 3 2
3 2 1

예제 출력 1

3
3
0
0

농부 존이 \((l=1,r=1)\), \((l=2,r=2)\), \((l=3,r=3)\) 중 하나를 고르면 검진을 받는 소가 없다. 이 연산들은 소들의 위치를 바꾸지 않는다는 점에 유의하라.

다음 세 연산은 한 마리의 소가 검진을 받게 한다.

• \(l=1,r=2\): 첫 번째 소와 두 번째 소의 순서를 뒤집으면 새로운 줄의 종은 \([3,1,2]\)가 된다. 첫 번째 소가 검진을 받는다.
• \(l=2,r=3\): 두 번째 소와 세 번째 소의 순서를 뒤집으면 새로운 줄의 종은 \([1,2,3]\)이 된다. 두 번째 소가 검진을 받는다.
• \(l=1,r=3\): 첫 번째 소부터 세 번째 소까지의 순서를 뒤집으면 새로운 줄의 종은 \([2,3,1]\)이 된다. 세 번째 소가 검진을 받는다.

예제 입력 2

3
1 2 3
1 2 3

예제 출력 2

0
3
0
3

세 마리의 소가 검진을 받게 하는 연산은 \((l=1,r=1)\), \((l=2,r=2)\), \((l=3,r=3)\)의 세 가지이다.

예제 입력 3

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

예제 출력 3

0
6
14
6
2
0
0
0

네 마리의 소가 검진을 받게 하는 연산은 \((l=4,r=5)\)와 \((l=5,r=7)\)의 두 가지이다.

서브태스크

출처

USACO 2025 January Contest, Bronze, Problem 3. Cow Checkups