Zadanie
Kockaté lampy
Počet bodov: 85
Žijeme v budúcnosti. A v budúcnosti už nie sme viazaní konvenciami symetrie, estetiky či fyziky. Čo to znamená pre nás? Pre našu spoločnosť? Že môžeme umiestniť žiarovky úplne kdekoľvek do priestoru. Bez žiadneho upevnenia či prívodu elektriny! Plne bezdrôtové, naozaj prelomové. A aby sme tých fyzikov dozaista nahnevali, uvažujme, že šírenie svetla má tvar kocky. Teda ak povieme, že žiarovka má silu S, znamená to, že vrhá svetlo na každý bod v priestore kocky s dĺžkou hrany S a stredom (ťažiskom) v danej žiarovke.
Hovorím to všetko preto, lebo si chcem osvetliť svoju izbu. Má tvar kvádra (presné rozmery vám poviem neskôr) a celé to už mám premyslené. Jedna žiarovka bude v tamtom rohu, jedna tuto položená na zemi, ďalšia sa bude vznášať nad dverami, … už ich len treba kúpiť. No a síce žijeme v budúcnosti bez fyzikálnych zákonov, avšak v každej budúcnosti platí trestný zákon. Čiže keďže si tie žiarovky nemôžem z obchodu len tak zobrať, tak by som ich chcel aspoň kúpiť za čo najmenej. To znamená kúpiť žiarovky s čo najmenšou silou postačujúcou na vysvietenie celej miestnosti.
Nebojte, uľahčím vám to. Nemusíte uvažovať žiadne odrazy svetla, sily žiaroviek sú iba celočíselené a čo je nadôležitejšie, všetky žiarovky musia mať rovnakú silu.
Formát vstupu
Na jednom vstupe bude viacero úloh. Každá úloha sa začína riadkom so štyrmi číslami - \(N\) (počet žiaroviek), \(Ix\), \(Iy\), \(Iz\) (rozmery izby). Nasleduje N riadkov, na \(i\)-tom z nich tri čísla \(Zx_i\), \(Zy_i\), \(Zz_i\) (pozícia žiarovky, pre každý rozmer \(r\) platí \(0 \leq Zr_i \leq Ir\)). Vstup je ukončený úlohou s \(N=Ix=Iy=Iz=0\).
Formát výstupu
Na výstup vypíšte \(N\) riadkov, na každom jedno celé číslo - silu žiaroviek pre danú úlohu.
Obmedzenia
Vstupy sú rozdelené do niekoľko sád, obtiažnosť sád sa stupňuje. V najťažšej sade pre každú úlohu platí \(1 \leq N \leq 50\), pre každý rozmer \(r\) je \(0 \leq Ir \leq 10^9\) a \(sum(N) \leq 10^3\). V skupinách sa bude vyskytovať niekoľko vstupov v ktorých bude iba zopár úloh, avšak \(N \leq 300\).
Príklad
Input:
2 4 4 8
2 2 2
2 2 5
2 4 4 8
2 2 2
2 2 6
0 0 0 0Output:
6
4