AlgoLiga 2018

Widok rozgwieżdżonego nieba inspirował ludzi od tysiącleci. Wyróżniają się te szczególnie jasne gwiazdy (jak Syriusz czy Wega), a wokół niezliczone ilości innych gwiazd. Wiele z nich jest naszymi bliskimi sąsiadami, a niektóre (jak Deneb) są tak ogromne, że doskonale widać je z tysięcy lat świetlnych. Joanna niemal co wieczór patrzy na niebo i marzy o przeróżnych rzeczach: dalekich podróżach, księciu z bajki i takich tam. Jest ona jednak nie tylko romantyczką, ale również umysłem ścisłym. Analizuje obrazy nieba za pomocą teleskopu i komputera. Potrzebuje oprogramowania, które będzie wyznaczać najjaśniejsze gwiazdy w poszczególnych sektorach nieba. A to już zadanie w sam raz dla Ciebie.

Wejście

W pierwszej linii wejścia podana jest liczba n gwiazd oraz liczba m zapytań (1<=n, m<=100000). W kolejnych n liniach podane są informacje o poszczególnych gwiazdach oddzielone spacjami. W każdej z linii są to kolejno:

• nazwa o długości poniżej 15 znaków złożona z wielkich liter alfabetu angielskiego i/lub cyfr
• deklinacja podana w stopniach (zakres 0-89) i minutach (zakres 0-59) wraz z półkulą (N-północna, S-południowa) podana w formacie SSMM - analogiczna do szerokości geograficznej
• rektascencja podana w godzinach (zakres 0-23) i minutach (zakres 0-59) w formacie GGMM - analogiczna do długości geograficznej
• jasność względna j gwiazdy podana z dokładnością do dwóch miejsc po przecinku (-2<=j<10).

W kolejnych m liniach podane są zapytania. W każdej z nich po cztery napisy: dekl1, dekl2, rekt1, rekt2 kodujące deklinację początkową sektora, deklinację końcową, rektascencję początkową sektora i rektascencję końcową. Deklinacja dekl2 jest bardziej wysunięta na południe od dekl1 lub jej równa. Rektascencja rekt2 jest większa lub równa rektascencji rekt1.

Wyjście

W każdej z m linii wyjścia ma się pojawić odpowiedź dla poszczególnych zapytań: jasność względna (podana z dokładnością do 2 miejsc po przecinku) oraz nazwa najjaśniejszej gwiazdy  należącej do rozpatrywanego sektora nieba (oddzielone spacjami). Im niższa wartość jasności względnej, tym jaśniejsza gwiazda. Gwiazda należy do sektora jeżeli jej deklinacja zawiera się w przedziale <dekl1, dekl2> oraz jej rektascencja zawiera się w przedziale <rekt1, rekt2>. Jeżeli w sektorze istnieje więcej niż jedna gwiazda o maksymalnej jasności, to program ma wypisać tę o najmniejszej leksykograficznie nazwie. Można założyć, że nie istnieje więcej niż 150 gwiazd o danej jasności. Jeżeli w danym sektorze nie ma żadnych gwiazd, to program ma wypisać "BRAK".

Przyklad

Wejście:
15 5
ACHERNAR 5714S 0137 0.45
ALDEBARAN 1630N 0435 0.85
RIGEL 0812S 0514 0.18
CAPELLA 4559N 0516 0.71
BETELGEUSE 0724N 0555 0.45
CANOPUS 5241S 0623 -0.62
SIRIUS 1642S 0645 -1.43
PROCYON 0513N 0739 0.38
ACRUX 6305S 1226 0.77
SPICA 1109S 1325 0.98
HADAR 6022S 1403 0.61
ARCTURUS 1911N 1415 -0.10
RIGELKENT 6050S 1439 0.01
VEGA 3846N 1836 0.03
ALTAIR 0852N 1950 0.77
4244S 8822S 1028 1706
5325N 8045S 1500 1919
2100S 8338S 0131 1335
3942S 5150S 2353 2353
0713S 5205S 0325 1750

Wyjście:
0.01 RIGELKENT
0.03 VEGA
-0.62 CANOPUS
BRAK
-1.43 SIRIUS