시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 0 0 0 0.000%

문제

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 <= 105 , 0 <= S <= 109 ) oznaczające początkowy rozmiar zbioru 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 PX i PY (-109 <= PXPY <= 109) oznaczających punkt o współrzędnych PXPY. 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 PX PY
  • 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.

예제 입력 1

1
5 1
1 1
1 3
2 2
3 2
3 3
7
ZNAJDZ
USUN 1 3
ZNAJDZ
USUN 2 2
ZNAJDZ
USUN 3 3
ZNAJDZ

예제 출력 1

1 3
2 2
3 3
1 1