Dreptunghiul ABCD are laturile de lungimi w şi h, numere naturale pare. Acest dreptunghi este desenat pe o foaie de matematică şi este descompus în w ∙ h pătrate de latură 1. Vârfurile A, B, C şi D sunt plasate în colţurile unor pătrate de latură 1.
Se alege un punct P din interiorul dreptunghiului ABCD, situat în colţul unui pătrat de latură 1 şi se uneşte prin segmente de dreaptă cu cele patru colţuri ale dreptunghiului. Unele segmente intersectează pătrate de latură 1 în exact două puncte distincte, altele într-un singur punct.
Numim pătrat 2-intersectat, un pătrat de latură 1 intersectat de un segment în exact 2 puncte distincte. În dreptunghiul din figura alăturată, segmentul PA trece prin 3 pătrate 2-intersectate, segmentul PB trece prin 9 pătrate 2-intersectate, segmentul PC trece prin 13 pătrate 2-intersectate, iar segmentul PD prin 7.
Cerinţă
Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x1, x2,… xn. Punctul P se plasează, pe rând, în toate punctele interioare dreptunghiului ABCD care sunt colţuri ale unor pătrate de latură 1. Pentru fiecare valoare xi (1 ≤ i ≤ n), determinaţi numărul de segmente distincte care trec prin exact xi pătrate
Date de intrare
Fişierul de intrare intersectii.in conţine pe prima linie trei numere naturale w, h (reprezentând dimensiunile dreptunghiului) şi n. Următoarele n linii conţin câte un număr natural xi cu semnificaţia de mai sus.
Date de ieşire
Fişierul de ieşire intersectii.out va conţine n linii. Pe fiecare linie i va fi scris numărul de segmente care trec prin exact xi pătrate 2-intersectate, obţinute după plasarea punctului P în fiecare colţ al unui pătrat de latură 1 din interiorul dreptunghiului ABCD.
Restricţii
• 2 ≤ w , h ≤ 2000 numere naturale pare
• 2 ≤ n ≤ 100000
• Punctul P se alege doar în interiorul dreptunghiului.
Exemple
intersectii.in
intersectii.out
Explicaţii
4 6 2
3
5
12
4
Se pot obţine 12 segmente care trec prin exact 3 pătrate 2-intersectate şi 4 segmente care trec prin exact 3 pătrate 2-intersectate.
