AlgoLiga 2018

Wdrażany przez CMOS system automatycznych pomiarów składników pogody jeszcze nie działa. Stacje pomiarowe są już rozmieszczone i znamy ich położenie we współrzędnych biegunowych względem stacji odbiorczej, ale nie ma jeszcze odpowiedniego oprogramowania do analizy uzyskiwanych danych. To właśnie zadanie, jakie postawiono przed Bajtłomiejem. W pierwszej fazie ta analiza dotyczyć ma jedynie pomiarów temperatury. Trzeba opracować program, który będzie rejestrował otrzymywane wyniki pomiarów oraz (na żądanie) szybko generował raport na temat maksymalnej, minimalnej i średniej temperatury w wybranym sektorze (w kształcie wycinka pierścienia kołowego).

Wejście

W pierwszej linii jedna liczba całkowita N oznaczająca liczbę stacji pomiarowych (1 ≤ N ≤ 10⁶).

W kolejnych N liniach po dwie liczby całkowite d i a określające położenie każdej ze stacji pomiarowych o numerach od 1 do N we współrzędnych biegunowych (najpierw odległość, a następnie kierunek w jakim znajduje się stacja pomiarowa względem stacji odbiorczej; 0 < d ≤ 10⁴, 0 ≤ a < 360). W jednym punkcie znajdować się może tylko jedna stacja.

Nastepnie nieokreślona liczba linii (nie więcej niż 2·10⁵), a w każdej z nich jedna z dwóch informacji: zarejestrowany wynik pomiaru temperatury lub polecenie wygenerowania raportu.
Wynik pomiaru ma postać: P i t, gdzie i to numer stacji pomiarowej (1 ≤ i ≤ N), a t - temperatura zmierzona z dokładnością do jednego miejsca po przecinku (-10⁸ ≤ t ≤ 10⁸) .
Polecenie wygenerowania raportu ma postać: R d₁ d₂ a₁ a₂, gdzie d₁, d₂, a₁ i a₂ to liczby całkowite oznaczające położenie sektora, którego ma dotyczyć raport (0 < d₁ ≤ d₂ ≤ 10⁵, 0 ≤ a₁, a₂ < 360). Jeśli a₁ ≤ a₂ to raport ma być stworzony na podstawie wyników ostatnich pomiarów ze stacji o współrzędnych (d,a), takich że ((d₁ ≤ d ≤ d₂) ∧ (a₁ ≤ a ≤ a₂)). Jeśli a₁ > a₂ to raport ma być stworzony na podstawie wyników ostatnich pomiarów ze stacji o współrzędnych (d,a), takich że ((d₁ ≤ d ≤ d₂) ∧ ((a ≥ a₁) ∨ (a ≤ a₂))).

Wyjście

Dla każdego polecenia wygenerowania raportu w osobnej linii trzy wartości: min, max i avg, gdzie: min - minimalna temperatura zarejestrowana w sektorze, max - maksymalna temperatura zarejestrowana w sektorze, avg - średnia temperatura obliczona z ostatnich pomiarów ze stacji leżących w sektorze. Wartości min i max powinny zostać podane z dokładnością do jednego, a avg - do sześciu miejsc po przecinku. Jeśli w analizowanym sektorze nie zarejestrowano dotychczas żadnych pomiarów, należy na wyjściu wypisać 'BRAK DANYCH'.

Przykład

Wejście:
4
2 40
7 190
1 135
3 359
P 1 10.1
R 1 10 90 180
P 4 4.9
R 2 8 350 40
R 1 7 130 200
P 3 -5.5
P 2 11.0
R 1 3 0 359 
P 4 0.0
R 1 20 180 179
R 3 3 359 0

Wyjście:
BRAK DANYCH
4.9 10.1 7.500000
BRAK DANYCH
-5.5 10.1 3.166667
-5.5 11.0 3.900000
0.0 4.9 0.000000