7. Istota čistoty

V T2 je špinavo. Dávid tam síce z času na čas povysáva, no Marcelovi to nestačí. Ako správny zdravotník si je vedomý toho, že pre odstránenie mikróbov bude nutné použiť niečo silnejšie. Doniesol si teda svoj tepovač a všetky koberce za doobedie dôkladne vyčistil.

Vtom si ale spomenul na ďalšiu nepríjemnosť. Totiž, vo vlhkom prostredí sa dobre darí plesniam. Zobral teda koberce a dal ich sušiť na slnečný trávnik. Trávnik je však malý a koberce sa nezmestia vedľa seba. Niektoré teda naukladal jeden na druhý. Nechcel ale, aby to bolo až príliš chaotické, nuž sa žiadne dva koberce nedotýkajú stranami ani rohmi. Môže však byť menší koberec položený na väčšom, alebo naopak.

Na slnečnom trávniku sa zvyknú hrávať deti. Nejaké koberce im vôbec neprekážajú. Keďže ale boli mokré, jedno z detí sa pošmyklo a rozsypalo po celom trávniku lentilky. Voda v kobercoch začala rozpúšťať farebnú cukrovú polevu. Pod každou lentilkou farba z polevy presiakla cez všetky koberce až po trávnik.

Keď si tú hrôzu Marcel všimol, prišlo mu zle. Potom si ale uvedomil, že sa vlastne nič zlé nestalo a začal namiesto toho rozmýšľať, koľko rôznych lentilkových farieb je na každom z kobercov. Je ale veľmi unavený z toľkého úmorného tepovania. Keby mu len niekto s touto úlohou pomohol…

Úloha

Marcel vám povedal, ako rozmiestnil koberce. Koberce sa nepretínajú ani nedotýkajú stranami ani rohmi. Dva koberce môžu byť navzájom nad sebou iba ak je jeden z nich úplne obsiahnutý v druhom a nedotýkajú sa stranami. Teda môže sa stať že je menší pod väčším, ale aj to, že je väčší pod menším a dokonca môže byť celá kopa kobercov medzi nimi (pričom každá dvojica v tejto kope spĺňa tieto pravidlá).

Koberce sú obdĺžnikové a sú poukladané tak, aby ich strany boli rovnobežné s osami \(x\) a \(y\).

Ďalej vám povedal súradnice a farby jednotlivých lentiliek. Farieb môže byť mnoho, no môže byť viac lentiliek tej istej farby.

Vašou úlohou je povedať Marcelovi, koľko rôznych farieb z lentiliek sa dostalo na ktorý koberec.

Formát vstupu

Na prvom riadku vstupu sú dve čísla \(n\) a \(m\) - počet kobercov a počet lentiliek. Platí, že \(1 \leq n, m \leq 10^5\).

Nasleduje \(n\) riadkov. Na \(i\)-tom z nich je popis \(i\)-teho koberca. Tento popis pozostáva zo 4 čísiel \(1 \leq x_1, y_1, x_2, y_2 \leq 10^9\) - súradníc ľavého dolného a pravého horného rohu. Môžete predpokladať, že \(x_1 < x_2\) a tiež \(y_1 < y_2\).

Na \(j\)-tom z ďalších \(m\) riadkov je popis \(j\)-tej lentilky. Pozostáva z 3 čísiel \(1 \leq x, y, f \leq 10^9\) - súradníc lentilky a jej farby.

Formát výstupu

Vypíšte \(n\) riadkov. Na \(i\)-tom z nich bude jedno číslo - počet rôznych farieb, ktoré lentilky pridali na \(i\)-ty koberec.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklad

Input:

3 3
1 1 10 10
2 2 9 9
4 4 6 8
2 10 1
2 9 2
5 7 3

Output:

3
2
1