eprubete

În laboratorul de chimie, Silviu are $N$ eprubete așezate pe un stativ și numerotate de la stânga la dreapta cu numere de la $1$ la $N$. Fiecare eprubetă $i$ are o capacitate de $P_i$ picături de substanță $i$. O picătură din substanța $1$ se obține picurând de la un robinet special instalat în acest scop. O picătură din oricare dintre substanțele $2$, $3$, $4$ și $5$ se obține consumând câte o picătură din fiecare eprubetă din stânga eprubetei. Pentru fiecare din celelalte substanțe $i \geq 6$ sunt cunoscute câte patru eprubete situate în stânga sa, iar pentru a obține o picătură din substanța $i$ se consumă câte o picătură din fiecare dintre cele patru eprubete. O picătură de substanță se obține în exact o secundă indiferent de substanță. Silviu vrea să umple toate eprubetele și pentru asta folosește în mod repetat următoarea regulă: se alege $i$ ca fiind prima eprubetă de la stânga la dreapta care nu este plină și se obțin una câte una cât mai multe picături în acea eprubetă. Observați că aceste picături vor tot fi obținute până când, fie se umple complet eprubeta $i$, fie se golește complet măcar una din eprubetele din care se consumă substanță pentru a obține substanța $i$ (desigur, robinetul folosit pentru a umple eprubeta $1$ nu se golește niciodată). La fiecare secundă începând cu $1$ și până când se umplu toate eprubetele se va obține exact o picătură dintr-o anumită substanță.

Cerință

Cunoscând $N$, capacitățile eprubetelor și pentru fiecare eprubetă $i \geq 6$ cele patru substanțe necesare pentru a obține substanța $i$, să se răspundă la $Q$ întrebări de forma "Din ce substanță se obține o picătură la secunda $S$?".

Date de intrare

Prima linie va conține $N$, numărul de eprubete. A doua linie va conține $N$ numere separate prin câte un spațiu: $P_1 \ P_2 \ \dots \ P_N$, reprezentând capacitățile eprubetelor. Următoarele $N - 5$ linii vor conține câte patru numere reprezentând, în ordinea liniilor, substanțele necesare pentru a obține substanțele $6, 7, \dots, N$. Următoarea linie va conține numărul $Q$ al întrebărilor la care trebuie să se răspundă. Următoarele $Q$ linii vor conține câte o valoare $S$, secunda pentru care trebuie să se răspundă la întrebare.

Date de ieșire

Se vor afișa $Q$ linii, fiecare conținând răspunsul la câte o întrebare, în ordinea dată la intrare.

Restricții și precizări

• $10 \leq N \leq 1 \ 000$;
• $10 \leq N \cdot Q \leq 10 \ 000 \ 000$;
• $1 \leq P_i \leq 100 \ 000$ pentru $1 \leq i \leq N$;
• Pentru fiecare eprubetă $i \geq 6$, cele patru eprubete necesare pentru a obține substanța $i$ sunt situate strict în stânga eprubetei $i$, sunt distincte două câte două, și sunt date în ordine crescătoare.
• Se garantează că, pentru fiecare întrebare, secunda $S$ nu depășește timpul total în care se umplu toate eprubetele.
• Se garantează că timpul total în care se umplu toate eprubetele nu depășește $10^{18}$.

Mai sus, toate afirmațiile despre $P_i$ se referă la toate eprubetele $i$ cu $1 \leq i \leq N$.

Exemplul 1

eprubete.in

10
1 1 1 1 1 1 1 1 1 1
1 2 4 5
2 3 5 6
1 3 4 6
2 5 6 7
1 4 5 9
5
325
200
277
20
200

eprubete.out

2
7
9
3
7

Explicație

În primul exemplu, pentru a patra întrebare trebuie să răspundem cu substanța ce se obține la secunda $20$. Răspunsul este $3$ deoarece în primele $20$ de secunde se obțin în ordine următoarele substanțe: $1$, $2$, $1$, $3$, $1$, $2$, $1$, $4$, $1$, $2$, $1$, $3$, $1$, $2$, $1$, $5$, $1$, $2$, $1$, $3$.

Exemplul 2

eprubete.in

10
4 3 4 1 3 1 2 2 2 2
1 2 3 4
1 4 5 6
1 2 5 7
2 3 4 5
4 7 8 9
5
21
13
27
225
184

eprubete.out

1
3
4
4
8

Explicație

În al doilea exemplu, în primele $30$ de secunde se obțin în ordine următoarele substanțe: $1$, $1$, $1$, $1$, $2$, $2$, $2$, $1$, $1$, $1$, $3$, $3$, $3$, $1$, $1$, $1$, $2$, $2$, $2$, $1$, $1$, $1$, $3$, $1$, $2$, $1$, $4$, $1$, $2$, $1$. Astfel, la secunda $21$ se obține substanța $1$, la secunda $13$ se obține substanța $3$, iar la secunda $27$ se obține substanța $4$.

Exemplul 3

eprubete.in

10
1 1 69 91 16 59 72 1 13 69
1 3 4 5
1 3 5 6
1 5 6 7
1 4 7 8
1 4 6 9
5
6518
6778
4438
21750
7364

eprubete.out

7
8
7
9
9