Fişierul intrare/ieşire:geamuri.in, geamuri.outSursăinfo-arena 1.0
AutorMihnea GiurgeaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Geamuri

Enervat de atatea probleme de pe InfoArena care nu-i ieseau si de atatea runde de GInfo cu probleme indentice, Geminski isi ia pistolul si pleaca sa impuste niste geamuri. Ajuns la fata locului, constata ca se afla in fata a N geamuri dreptungiulare, fiecare bine delimitat in raport cu sistemul cartezian ortogonal. Geminski are la el M gloante. Cand se decide sa traga un glont, el isi stabileste un punct bine delimitat in raport cu sistemul cartezian ortogonal, dupa care trage! Geminski are totusi unele limitari, astfel ca nu poate trage decat din puncte cu coordonate cuprinse intre 1 si C. Fiecare geam ce contine acel punct se va sparge. Geminski vrea ca atunci cand trage cu glontul al i-lea, sa sparga exact Ki geamuri.

Cerinta

Scrieti un program care sa determine pentru fiecare glont pe care il trage Geminski din cate pozitii il poate trage astfel incat sa sparga exact Ki geamuri.

Date de intrare

Primele doua linii ale fisierului de intrare geamuri.in contin numarele intregi C, respectiv N. Urmatoarele N linii contin cate 4 numere intregi x0, y0, x1, y1 reprezentand coordonatele geamurilor date prin coltul stanga-jos si dreapta-sus (1 ≤ x0 ≤ x1 ≤ C, 1 ≤ y0 ≤ y1 ≤ C). Urmatoare linie contine numarul intreg M, iar urmatoarele M linii numerele Ki (1 ≤ i ≤ M), cate unul pe linie.

Date de iesire

Fisierul de iesire geamuri.out va contine M linii, cu numarul cautat pe fiecare linie.

Restrictii si precizari

  • 1 ≤ C ≤ 1024
  • 0 ≤ Ki ≤ N ≤ 50.000
  • 1 ≤ M ≤ 50.000
  • Geamurile se pot suprapune

Exemplu

geamuri.ingeamuri.out
8
3
2 2 5 4
5 3 6 8
4 4 7 6
2
3
2
1
7

Explicatii

Primul glont poate fi tras doar din (5, 4)
Al doilea din coordonatele (4, 4), (5, 3), (5, 5), (5, 6), (6, 4), (6, 5), (6, 6)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content