Descripción

En el año 30XX, debido a los constantes esfuerzos de científicos e ingenieros, la interacción entre diferentes planetas se vuelve muy activa. BitCuba es un castor que trabaja como embajador de un programa de intercambio. Su tarea consiste en introducir alimentos de la Tierra a los habitantes de diferentes planetas. Saldrá hacia el Planeta OCI a la ~1:00~ de la tarde.

Ahora, BitCuba está planeando introducir la panetela a los habitantes del Planeta OCI. La panetela ya fue cortada en varias piezas. La panetela es un bizcocho horneado hecho de harina, huevo, azúcar y jarabe de almidón.

La forma de la panetela es una caja rectangular horizontalmente larga. Se corta en N trozos. La longitud de la i-ésima pieza (~1 \le i \le N~) desde la izquierda es un número entero ~A_i~.

Hace un par de minutos, resultó que a los habitantes del Planeta OCI no les gustan los números enteros pares. Para hacer frente a con este problema, realizarás las siguientes operaciones secuenciales hasta que desaparezcan los trozos de longitud par.

1. Entre los trozos de longitud par, eliges el más a la derecha.
2. Corta el trozo elegido en dos trozos de igual longitud. Es decir, si la longitud de la pieza elegida es k, la cortas en dos trozos de longitud ~k/2~ . No mueva la posición de las piezas.

Tarea

Para confirmar si las operaciones se han realizado correctamente, BitCuba le hará preguntas. La j-ésima pregunta (~1 \le j \le Q~) es la siguiente.

• Después de realizar todas las operaciones, ¿cuál es la longitud de la pieza X j-ésima desde la izquierda? Dada la información de la panetela y las preguntas, escribe un programa que responda a las preguntas.

Entrada

Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

~N~

~A_1~

~A_2~

~...~

~A_N~

~Q~

~X_1~

~X_2~

~...~

~X_Q~

Salida

Escribe ~Q~ líneas en la salida estándar. La j-ésima línea (~1 \le j \le Q~) debe contener la respuesta a la j-ésima pregunta.

Restricciones

• ~1 \le N \le 200 000~.
• ~1 \le A_i \le 1 000 000 000 (1 \le i \le N)~.
• ~1 \le Q \le 200 000~.
• ~1 \le X_j \le 1 000 000 000 000 000 (= 10^{15}) (1 \le j \le Q)~.
• ~X_j~ ~\le~ ~X_{j+1}~ (~1 \le j \le Q - 1~).
• Una vez realizadas todas las operaciones, la panetela se corta en al menos ~X_Q~ trozos.

Subtareas

1. (25 puntos) ~A_i \le 8~ (~1 \le i \le N~).
2. (35 puntos) ~N \le 1 000~, ~Q \le 1 000~.
3. (40 puntos) No hay restricciones adicionales.

Entrada de Entrada

4
14
9
8
12
6
2
3
5
7
11
13

Ejemplo de Salida

7
9
1
1
1
3

Al principio, las longitudes de las piezas de la panetela son 14, 9, 8, 12 desde la izquierda.

Una vez realizadas todas las operaciones, la panetela se corta en 15 piezas. Las longitudes de las piezas son ~7~,~7~, ~9~, ~1~, ~1~, ~1~, ~1~, ~1~, ~1~, ~1~, ~1~, ~3~, ~3~,~3~, ~3~ desde la izquierda. Esta muestra de entrada satisface las restricciones de las subtareas 2, 3.