Fişierul intrare/ieşire:rox.in, rox.outSursăUrmasii lui Moisil 2015, Clasa a 9-a
AutorLiana TucarAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.5 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rox

Părinţii lui Rox au cumpărat de curând un teren care are N metri lăţime şi M metri lungime, pe care l-au împărţit în pătrate cu latura de un metru, denumite celule. Văzând planul terenului, lui Rox i-a venit o idee. Ea s-a decis să semene florile ei preferate în etape, pe U dintre parcele de teren. Denumirile florilor sunt litere mari ale alfabetului englez. O parcelă este un dreptunghi inclus în teren, cu laturile paralele cu ale terenului şi care conţine doar celule complete.

În fiecare etapă în care Rox seamănă flori, procedează astfel: alege o parcelă pentru care reţine indicii celulelor din stânga sus şi dreapta jos, stabileşte tipul florii pe care doreşte să o semene peste tot în parcelă, apoi scrie aceste informaţii pe o foaie de hârtie. Documentându-se pe Internet, Rox ajunge la concluzia că apare următorul fenomen ciudat: dacă într-o celulă se seamănă acelaşi tip de floare într-un număr par de etape, seminţele de acel tip pur şi simplu dispar.

Când finalizează semănatul, Rox le povesteşte părinţilor despre isprava ei. Entuziasmaţi, părinţii fetei îi pun mai multe întrebări de tipul ”Câte tipuri de flori au rămas semănate în celula de pe linia L şi coloana C?”

Cerinţă

Deoarece Rox a plantat foarte multe flori, ea nu poate să răspundă rapid întrebărilor părinţilor, aşa încât vă cere ajutorul şi vă va răsplăti efortul cu maxim 100 de puncte.

Date de intrare

Pe prima linie a fişierului rox.in se află 3 numere: N, M şi U, separate prin câte un spaţiu şi având semnificaţia din enunţ. Pe fiecare din următoarele U linii se află: L1 C1 L2 C2 T, separate prin câte un spaţiu şi reprezentând datele scrise de Rox pe foaie, corespunzătoare unei etape de semănat (coordonatele colţurilor din stânga sus şi dreapta jos ale parcelei şi T, tipul florii).

Pe linia U+2 se află Q, numărul de întrebari puse de părinţii lui Rox.

Pe fiecare din următoarele Q linii se află L C (coordonatele celulei despre care părinţii lui Rox vor informaţii).

Date de ieşire

Fişierul de ieşire rox.out va conţine Q linii. Pe fiecare dintre cele Q linii se vor afla răspunsurile la întrebările părinţilor lui Rox, în ordinea în care acestea au fost puse.

Restricţii

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ U ≤ 100000
  • 1 ≤ Q ≤ 100000
  • L1 ≤ L2; C1 ≤ C2
  • Iniţial pe teren nu era semănată nicio floare.
  • T reprezintă o literă mare a alfabetului englez.
  • Întrebările se pot repeta.
  • Datele de intrare nu necesită validare.
  • Pentru 15% din teste U × Q ≤ 3.000.000
  • Pentru 35% din teste N, M ≤ 100, U ≤ 300
  • Pentru 60% din teste N, M ≤ 800

Exemplu

rox.inrox.out
14 17 6
3 3 8 10 A
5 6 11 14 B
8 2 11 3 W
6 8 12 17 B
8 5 14 8 A
2 13 2 14 Z
4
4 5
7 9
5 10
8 3
1
1
2
2

Explicaţie

În celula (4,5) se seamănă floarea A care rămâne acolo .
În celula (7,9) se seamănă floarea A, apoi B, apoi iar B (la a doua semănare a florii de tipul B dispare floarea B). În final rămâne doar A.
În celula (5,10) se seamănă A şi B care rămân acolo.
În celula (8,3) se seamănă A şi W care rămân acolo.
În figura de mai jos sunt marcate cu ? celulele corespunzătoare întrebărilor.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?