8799번 - Zapytania 다국어

Należy przygotować program, który dla zadaniego zbioru punktów Z i wartości "tolerancji" S będzie wykonywał operacje dwóch rodzajów:

• Usuń zadany punkt ze zbioru Z
• Znajdź punkt górnolewy zbioru Z

Punkt górnolewy to położony najbardziej na lewo ( posiadający najmniejszą współrzędną x ) punkt spośród tych punktów, których współrzędna y jest mniejsza od współrzędnej y najwyżej położonego punktu w zbiorze o co najwyżej S. Jeśli jest wiele takich punktów, należy wybrać ten z nich, który leży najwyżej ( ma największą współrzędną y ).

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu pojedynczego zestawu znajdują się dwie oddzielone spacjami liczby naturalne N i S ( 1 <= N <= 10⁵ , 0 <= S <= 10⁹ ) oznaczające początkowy rozmiar zbioru Z i wartość "tolerancji". W kolejnych N liniach znajduje się lista punktów w zbiorze Z w postaci par ( po jednej w linii ) oddzielonych spacjami liczb całkowitych P_X i P_Y (-10⁹ <= P_X, P_Y <= 10⁹) oznaczających punkt o współrzędnych P_X, P_Y. Punkty na liście będą parami różne.

W kolejnej linii opisu pojedynczego zestawu znajduje się liczba naturalna M (1 <= M <= 2*10⁵ ) - liczba operacji do wykonania. Każda z kolejnych M linii jest jednej z dwóch postaci:

• USUN P_X P_Y
• ZNAJDZ

Znaczenie poszczególnych operacji jest opisane w treści zadania. Możesz założyć że punkt, który należy usunąć ze zbioru Z w momencie wydania polecenia znajduje się w zbiorze. Możesz założyć, że polecenie "znajdź" nie będzie wywoływane kiedy zbiór Z będzie pusty.

Dla każdego polecenia "znajdź" należy w osobnej linii wypisać współrzędne znalezionego punktu.