== include(page="template/taskheader" task_id="magnet") ==
Poveste și cerință...
!>problema/magnet?magnet_mic.jpg!
Ion a colecționat magneți de frigider cu cuvinte pe ei, până când a făcut rost de toate cuvintele de $K$ litere din mulțimea ${A, B, C, D}$. Apoi a așezat aceste cuvinte într-un pătrat, astfel:
* Cuvintele care încep cu litera A stau în sfertul din stânga-sus
* Cuvintele care încep cu litera B stau în sfertul din dreapta-sus
* Cuvintele care încep cu litera C stau în sfertul din stânga-jos
* Cuvintele care încep cu litera D stau în sfertul din dreapta-jos
* Fiecare din cele patru sferturi este dispus similar, împărțind cuvintele după a doua lor literă
* Ion procedează similar pentru fiecare din cele $K$ litere.
De exemplu, pentru $K$ = 3, dreptunghiul rezultat este
$AAA AAB ABA ABB BAA BAB BBA BBB$
$AAC AAD ABC ABD BAC BAD BBC BBD$
$ACA ACB ADA ADB BCA BCB BDA BDB$
$ACC ACD ADC ADD BCC BCD BDC BDD$
$CAA CAB CBA CBB DAA DAB DBA DBB$
$CAC CAD CBC CBD DAC DAD DBC DBD$
$CCA CCB CDA CDB DCA DCB DDA DDB$
$CCC CCD CDC CDD DCC DCD DDC DDD$
Apoi Ion își pune $Q$ întrebări de tipul: de câte ori apare litera $X$ în dreptunghiul delimitat de magneții $(l[~1~], c[~1~])$ și $(l[~2~], c[~2~])$ inclusiv?
h2. Date de intrare
Fișierul de intrare $magnet.in$ ...
Fișierul de intrare $magnet.in$ conține pe prima linie valorile întregi $K$ și [$Q$]. Următoarele $Q$ linii descriu câte o întrebare sub forma unui tuplu $X l[~1~] c[~1~] l[~2~] c[~2~]$.
h2. Date de ieșire
În fișierul de ieșire $magnet.out$ ...
În fișierul de ieșire $magnet.out$ se vor tipări răspunsurile la cele $Q$ întrebări, câte unul pe linie, în ordinea de la intrare.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ 20$
* $1 ≤ Q ≤ 100.000$
* Pentru 30% din teste, $1 ≤ K ≤ 10$ și $1 ≤ Q ≤ 2.000$
* $X ∈ { A, B, C, D }$ (întotdeauna litere mari)
* $1 ≤ l[~1~] ≤ l[~2~] ≤ 2[^K^]$
* $1 ≤ c[~1~] ≤ c[~2~] ≤ 2[^K^]$
h2. Exemplu
table(example).
|_. magnet.in |_. magnet.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
A 2 3 5 4
C 5 5 5 8
| 8
0
|
h3. Explicație
...
Dreptunghiul (2,3)-(5,4) conține șirurile $ABC ABD ADA ADB ADC ADD CBA CBB$. În total, acestea conțin 8 litere [$A$].
Dreptunghiul (5,5)-(5,8) conține șirurile $DAA DAB DBA DBB$. Acestea nu conțin nicio literă [$C$].
== include(page="template/taskfooter" task_id="magnet") ==
