Cow Checkups.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Las $N$ ~N~ $(1 \leq N \leq 7500)$ ~(1 \leq N \leq 7500)~ vacas del granjero Juan están formadas en una fila, con la vaca $1$ ~1~ al frente de la fila y la vaca $N$ ~N~ al final de la fila. Las vacas de GJ también pertenecen a muchas especies diferentes. Denota cada especie con un número entero del $1$ ~1~ al $N$ ~N~. La i-ésima vaca desde el frente de la fila es de la especie $a_i$ ~a_i~ $(1 \leq a_i \leq N)$ ~(1 \leq a_i \leq N)~.

GJ está llevando a sus vacas a un chequeo en un hospital bovino local. Sin embargo, el veterinario bovino es muy exigente y quiere realizar un chequeo a la i-ésima vaca en la fila, solo si es de la especie $b_i$ ~b_i~ $(1 \leq b_i \leq N)$ ~(1 \leq b_i \leq N)~.

GJ es perezoso y no quiere reordenar completamente a sus vacas. Realizará la siguiente operación exactamente una vez.

• Seleccionar dos enteros $l$ ~l~ y $r$ ~r~ tales que $1 \leq l \leq r \leq N$ ~1 \leq l \leq r \leq N~. Invertir el orden de las vacas que están entre la l-ésima y la r-ésima vaca en la fila, inclusive.

GJ quiere medir cuán efectiva es esta estrategia. Para cada $c=0...N$ ~c=0...N~, ayuda a GJ a encontrar el número de operaciones distintas $(l,r)$ ~(l,r)~ que resultan en exactamente $c$ ~c~ vacas siendo chequeadas. Dos operaciones $(l_1,r_1)$ ~(l_1,r_1)~ y $(l_2,r_2)$ ~(l_2,r_2)~ son diferentes si $l_1 \neq l_2$ ~l_1 \neq l_2~ o $r_1 \neq r_2$ ~r_1 \neq r_2~.

Entrada

La primera línea contiene un entero $N$ ~N~.
La segunda línea contiene $a_1,a_2,...,a_N$ ~a_1,a_2,...,a_N~.
La tercera línea contiene $b_1,b_2,...,b_N$ ~b_1,b_2,...,b_N~.

Salida

Imprime $N+1$ ~N+1~ líneas donde la i-ésima línea contiene el número de operaciones distintas $(l,r)$ ~(l,r)~ que resultan en que $i-1$ ~i-1~ vacas sean chequeadas.

Ejemplo #1 de Entrada

3
1 3 2
3 2 1

Ejemplo #1 de Salida

Si GJ elige $(l=1,r=1)$ ~(l=1,r=1)~, $(l=2,r=2)$ ~(l=2,r=2)~ o $(l=3,r=3)$ ~(l=3,r=3)~, entonces ninguna vaca será chequeada. Nota que esas operaciones no modifican la ubicación de las vacas. Las siguientes operaciones resultan en que una vaca sea chequeada.

• $l=1,r=2$ ~l=1,r=2~: GJ invierte el orden de la primera y segunda vaca, por lo que las especies de cada vaca en la nueva fila serán $[3,1,2]$ ~[3,1,2]~. Se chequeará la primera vaca.

• $l=2,r=3$ ~l=2,r=3~: GJ invierte el orden de la segunda y tercera vaca, por lo que las especies de cada vaca en la nueva fila serán $[1,2,3]$ ~[1,2,3]~. Se chequeará la segunda vaca.

• $l=1,r=3$ ~l=1,r=3~: GJ invierte el orden de la primera, segunda y tercera vaca, por lo que las especies de cada vaca en la nueva fila serán $[2,3,1]$ ~[2,3,1]~. Se chequeará la tercera vaca.