h2. Date de intrare

Fişierul de intrare $referat.in$ va contine pe prima linie $N$, $L$ si $P$. Pe urmatoarea linie vor fi $N$ numere naturale, al $i$-lea numar este S{~i~}, reprezentand lungimea cuvantului $i$.

Fişierul de intrare $referat.in$ va contine pe prima linie $N$, $L$ si $T$ (numarul de teste). Pe urmatoarea linie vor fi $N$ numere naturale, al $i$-lea numar este S{~i~}, reprezentand lungimea cuvantului $i$. Pe urmatoarele $T$ linii se va afla cate un numar $P$, reprezentand lungimea cuvantului pe care dorim sa il inseram in text.

h2. Date de ieşire

Fişierul de ieşire $referat.out$ va contine un singur numar natural reprezentand numarul de pozitii in care poate sa fie introdus noul cuvant astfel incat baietii sa obtina cel putin un rand in plus.

Fişierul de ieşire $referat.out$ va contine $T$ linii cu exact un numar natural, reprezentand numarul de pozitii in care poate sa fie introdus noul cuvant astfel incat baietii sa obtina cel putin un rand in plus pentru testul respectiv.

h2. Restricţii
* $1 ≤ N ≤ 100.000$

* $1 ≤ T ≤ 10$

* $1 ≤ P,S{~i~} ≤ L ≤ 1.000.000.000$

* Pentru $30%$ din teste $N ≤ 1000$

h2. Exemplu
table(example). |_. referat.in |_. referat.out |

|5 10 4

|5 10 1

7 1 5 2 8

4

|3

|

|
 
h2. Explicatii
 
Copii au $5$ cuvinte de lungime $7, 1, 5, 2, 8$, sa zicem urmatoarele cuvinte: $Sambata$ $A$ $Venit$ $Cu$ $Beatrice$, iar cuvantul pe care vrem sa-l introducem este $Rece$.
Initial textul pus pe linii de lugime maxim $10$ este:
 
$SambataA$
$VenitCu$
$Beatrice$
 
In functie de unde introducem cuvantul $Rece$ se obtin urmatoarele distribuiri pe linii:
 
$Rece$
$SambataA$
$VenitCu$
$Beatrice$
 
$Sambata$
$ReceAVenit$
$CuBeatrice$
 
$SambataA$
$ReceVenit$
$CuBeatrice$
 
$SambataA$
$VenitRece$
$CuBeatrice$
 
$SambataA$
$VenitCu$
$Rece$
$Beatrice$
 
si
 
$SambataA$
$VenitCu$
$Beatrice$
$Rece$
Observam ca doar daca introducem cuvantul $Rece$ la inceput, fix inainte de cuvantul $Beatrice$, si la final numarul de linii creste cu 1. Astfel raspunsul este 3.

== include(page="template/taskfooter" task_id="referat") ==