Busy Beaver ha decidido postularse para presidente. Desafortunadamente, su único rival, Lazy Lemur, es demasiado fuerte y Busy Beaver no puede ganar por medios normales. Por lo tanto, hace lo que todo buen político hace: ¡manipular la elección mediante el gerrymandering!
El país de Busy Beaver consta de $N$ ciudades en una fila numeradas del $1$ al $N$. Cada ciudad vota por Lazy Lemur o por Busy Beaver como presidente, representado por un $0$ si el voto es para Lazy Lemur y un $1$ si el voto es para Busy Beaver. Sin embargo, Busy Beaver puede dividir las $N$ ciudades en $K$ bloques no vacíos de ciudades contiguas, donde cada bloque es un distrito. Para cada valor de $K$ desde $1$ hasta $N$, Busy Beaver desea maximizar el número de distritos que tienen estrictamente más votos para él que para Lazy Lemur.
¿Puedes ayudar a Busy Beaver a encontrar el número máximo de distritos con estrictamente más votos para $K = 1, \dots, N$?
Entrada
Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 10^4$). A continuación se presenta la descripción de los casos de prueba.
La primera línea de cada caso de prueba contiene un entero $N$ ($1 \le N \le 10^5$) que describe el número de ciudades.
La segunda línea de cada caso de prueba contiene una cadena $s$ de $0$s y $1$s de longitud $N$, donde $s_i$ siendo $0$ denota que Lazy Lemur gana el voto de la $i$-ésima ciudad y $1$ denota que Busy Beaver gana el voto de la $i$-ésima ciudad, para cada $i$ desde $1$ hasta $N$.
Se garantiza que la suma de $N$ en todos los casos de prueba no supera $10^5$.
Salida
Para cada caso de prueba, imprime $N$ enteros, donde el $K$-ésimo entero representa el número máximo de distritos con estrictamente más votos para Busy Beaver después de dividir las ciudades en $K$ bloques no vacíos de ciudades contiguas.
Puntuación
- (10 puntos) La suma de $N$ en todos los casos de prueba es como máximo $100$.
- (25 puntos) La suma de $N$ en todos los casos de prueba es como máximo $3000$.
- (65 puntos) La suma de $N$ en todos los casos de prueba es como máximo $10^5$.
Ejemplos
Entrada 1
3 3 000 5 01101 8 11011011
Salida 1
0 0 0 1 1 2 2 3 1 2 3 4 4 5 5 6
Nota
Hay $3$ casos de prueba.
En el primer caso de prueba, Busy Beaver nunca puede ganar ningún distrito porque cada ciudad vota por Lazy Lemur.
En el segundo caso de prueba, hay $5$ ciudades. Para $K = 3$, Busy Beaver puede ganar $2$ distritos dividiendo las ciudades en distritos usando los subarreglos $[1, 3]$, $[4, 4]$ y $[5, 5]$. En $[1, 3]$, $2$ de las $3$ ciudades votan por él. Pierde el subarreglo $[4, 4]$ porque la única ciudad allí no vota por él. Gana el subarreglo $[5, 5]$ porque la única ciudad allí vota por él. Se puede demostrar que Busy Beaver no puede ganar más de $2$ distritos.
Nótese que dividir en los subarreglos $[1, 2]$, $[3, 4]$ y $[5, 5]$ solo le daría $1$ distrito ganado. En particular, solo gana una ciudad en cada uno de $[1, 2]$ y $[3, 4]$, y por lo tanto no obtiene una mayoría estricta en ninguno de los dos distritos.