Durante mucho tiempo has sido un gran fan de Bytelandia. Casi al mismo tiempo, los miembros de tu familia te han estado diciendo que todos estos juegos son una pérdida de dinero. Usted está seguro de que es debido a su ¡falta de habilidad! Tienes un plan brillante y todos te verán ganando el juego pronto.

Hay muchos tipos de juegos. Usted está interesado en uno de ellos: Bitlotto. La elección fue simple, ya que es el tipo de juego que se ofrece con mayor facilidad: en cada día se dibuja exactamente un número al azar. Tomaste notas del Los resultados de los sorteos en ~n~ días consecutivos y obtuvieron una secuencia ~a_1, a_2,... , a_n~. Está seguro de que hay algun patrón en esta secuencia, especialmente en intervalos de ~l~ días consecutivos. Tu familia todavía no te cree, así que la única manera de convencerlos es usar matemáticas sólidas.

Hay ~n-l+1~ intervalos de días de duración ~l~. El ~i-th~ intervalo comienza en la posición ~i~, por lo que contiene elementos ~a_i, a_{i+1},... ,a_{i+l-1}~. La distancia entre dos intervalos es el número de desajustes en sus correspondientes posiciones. En otras palabras, para el ~x-th~ e ~y-th~ intervalo es el número de posiciones ~i~ ~(0 \le i < l)~, como que ~a_{x+i}~ y ~a_{y+i}~ son diferentes. Finalmente, definimos dos intervalos para ser ~k~-similares si su distancia es como máximo ~k~.

Tarea

Hay una secuencia fija y un entero ~l~. Se le dan ~q~ consultas. En cada consulta, se le da un número entero ~k_j~ y para cada uno de los intervalos ~n-l+1~ debe encontrar el número de intervalos de la misma longitud que son ~k_j~-similar a este intervalo (sin contar este intervalo en sí).

Entrada

La primera línea de la entrada estándar contiene dos enteros separados por espacios ~n~ y ~l~ ~(1 \le l \le n \le 10 000)~, el número de días y duración de los intervalos analizados.

La segunda línea contiene ~n~ enteros separados por espacios ~a_1, a_2,..., a_n~ ~(1 \le a_i \le 10^9)~, donde a ~i~ es el número que se dibujó en el ~i-th~ día.

La tercera línea contiene un entero ~q~ ~(1 \le q \le 100)~, el número de consultas. Cada una de las siguientes ~q~ líneas contiene un entero ~k_j~ ~(0 \le k_j \le l)~, el parámetro de similitud para la ~j-th~ consulta.

Salida

Imprimir ~q~ lineas. La ~j-th~ línea debe contener ~n-l+1~ enteros separados por espacios que son la respuesta a la ~j-th~ consulta. El ~i-th~ número en una línea debe ser el número de otros intervalos que son ~k_j~-similares al ~i-th~ intervalo.

Ejemplo de Entrada

6 2
1 2 1 3 2 1
2
1
2

Ejemplo de Salida

2 1 1 1 1
4 4 4 4 4

Explicación del ejemplo:

En el ejemplo anterior hay cinco intervalos de longitud 2:

• El primer intervalo contiene los números ~1~ ~2~.

• El segundo intervalo contiene los números ~2~ ~1~

• El tercero intervalo contiene los números ~1~ ~3~

• El cuarto intervalo contiene los números ~3~ ~2~

• El quinto intervalo contiene los números ~2~ ~1~

Hay dos consultas.

La primera consulta tiene ~k = 1~. El primer y el tercer intervalo ~[1~ ~2]~ y ~[1~ ~3]~ difieren solo en la segunda posición, tal que la distancia entre ellos es ~1~. Del mismo modo, el primer y cuarto intervalo ~[1~ ~2]~ y ~[3~ ~2]~ difieren solo en la primera posición, por lo que la distancia es ~1~. Estos son los únicos dos intervalos que son ~1~-similar al primer intervalo, por lo que el primer número a imprimir es ~2~.

En la segunda consulta se nos da ~k = 2~. Todos los pares de intervalos son ~2~-similar.

Calificación

El conjunto de prueba se divide en las siguientes subtareas con restricciones adicionales. Pruebas en cada una de las subtareas. consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea: 1 Restricciones: ~n \le 300~; Puntos: ~25~

Subtarea: 2 Restricciones: ~n \le 2000~; Puntos: ~20~

Subtarea: 3 Restricciones: ~q = 1~, ~k_1 = 0~; Puntos: ~20~

Subtarea: 4 Restricciones: ~q = 1~; Puntos: ~15~

Subtarea: 5 sin restricciones adicionales; Puntos: ~20~