Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a, skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na [email protected].
Mapu už máme a tak nám zostáva posledná vec pred tým, ako sa môžeme vybrať preč. Pred každou dlhou cestou je veľmi dôležité poriadne sa napapať. Naša pani kuchárka Miška si však zabudla so sebou zobrať suroviny, a tak ich potrebujeme zohnať z lokálneho skladu domorodcov. Tento sklad vyzerá veľmi špecificky, sú v ňom dve dlhé poličky pod sebou a veci sú na nich vždy umiestnené v dvojiciach pod sebou.
Aby sa Miška nemusela naťahovať k hornej poličke, dohodla sa so Štepim, že mu bude diktovať suroviny a on ich bude z poličiek skladať. Avšak hneď pri prvej surovine po ktorej Štepi siahol Miška skoro skolabovala. Pýtate sa prečo? Štepi išiel zobrať syr, pod ktorým bola šunka.
Miška totiž pochádza z veľmi poverčivej rodiny a jedna takáto povera hovorí, že ak použijete surovinu, pod ktorou nie je rovnaká surovina, zaručíte si tým otravu jedlom. Štepimu to síce prišlo ako blbosť, rozhodol sa však rešpektovať Miškinu poverčivosť a používať iba suroviny, pod ktorými je tá istá surovina.
Týmto sa ale objavil nový problém - koľko surovín vôbec môžu použiť? Keďže poličky sú veľmi dlhé, potrebuje so zrátaním takýchto surovín vašu pomoc.
Máme dve poličky umiestnené pod sebou a na každej z nich je $n$ surovín. Tieto suroviny sú umiestnené v dvojiciach pod sebou. Pomôžte Štepimu a Miške zistiť koľko sa v sklade nachádza surovín, pod ktorými je rovnaká surovina.
Každá surovina je reprezentovaná nezáporným celým číslom. Keďže poličky môžu byť veľmi dlhé, ich obsah dostanete vo forme úsekov, ktoré obsahujú rovnakú surovinu.
V prvom riadku vstupu je číslo $N$ - počet surovín na každej poličke.
V druhom riadku sa nachádza číslo $X$ - počet úsekov prvej poličky.
Nasleduje $X$ riadkov popisujúcich úseky prvej poličky. V každom z nich je trojica čísel $z_i$, $k_i$ a $s_i$ - označujúca začiatok a koniec úseku (vrátane) a surovinu, ktorá sa v ňom nachádza.
Na ďalšom riadku je číslo $Y$ - počet úsekov druhej poličky. Za ním nasleduje $Y$ riadkov popisujúcich úseky druhej poličky v rovnakom formáte ako úseky prvej poličky.
Je zaručené, že sa žiadne dva úseky na jednej poličke neprekrývajú a že úseky pokrývajú celú poličku. Úseky nemusia byť zoradené v poradí od začiatku po koniec poličky. Vždy platí $1 \leq X, Y \leq N$, $1 \leq z_i \leq k_i \leq N$ a $1 \leq s_i \leq 10^9$.
Existujú 4 sady vstupov, obmedzenia v nich a ich bodovanie sú nasledovné:
| Sada | 1 | 2 | 3 |
|---|---|---|---|
| Body | 10 | 20 | 70 |
| $1 \leq N \leq$ | $100$ | $10^6$ | $10^{15}$ |
| $1 \leq X+Y \leq N$ | $200$ | $2*10^6$ | $5*10^5$ |
Pozor, v sade 3 sa môžu vyskytovať veĺmi veľké hodnoty, ktoré sa nezmestia do
štandardných 32-bitových premenných. V jazykoch iných ako Python je preto potrebné
použiť 64-bitové premenné (long long v C++, int64 v Pascale, a pod.).
Vypíšte jeden riadok a v ňom jedno celé číslo odpovedajúce počtu surovín, pod ktorými je rovnaká surovina.
5
4
1 1 1
2 2 3
3 3 2
4 5 1
2
1 2 3
3 5 1
3
| 1 | 3 | 2 | 1 | 1 |
| 3 | 3 | 1 | 1 | 1 |
5
2
1 3 1
4 5 2
2
1 2 1
3 5 2
4
| 1 | 1 | 1 | 2 | 2 |
| 1 | 1 | 2 | 2 | 2 |