Archiwum zadań programistycznych WWSI

Jarek razem ze swoimi dwoma przyjaciółmi Darkiem i Markiem rozpoczyna w tym roku naukę w szkole podstawowej. W szkole każdy uczeń otrzymuje swój unikalny n literowy identyfikator. Darek i Marek otrzymali już swoje identyfikatory. Oznaczmy je odpowiednio jako D i M. Jarek cały czas czeka na swój, oznaczmy go jako J. Nasz bohater bardzo chciałby, aby jego identyfikator spełniał następujące nierówności w porządku leksykograficznym: D < J < M. Oprócz tego liczba wyrazów w porządku leksykograficznym pomiędzy identyfikatorami D i J, a J i M powinna być identyczna.

Twoim zadaniem jest wyznaczenie identyfikatora J spełniającego powyższe warunki albo stwierdzenie, że taki nie istnieje.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10⁵] określająca liczbę zestawów danych. W kolejnych t liniach znajdują się zestawy danych. Każdy zestaw danych składa się z dwóch wyrazów oddzielonych pojedynczą spacją. Pierwszy z nich to identyfikator Darka D, drugi zaś to identyfikator Marka M. Długość obydwu identyfikatorów jest identyczna i zawiera się w przedziale [1;10]. Gwarantujemy, że D < M w porządku leksykograficznym. Identyfikatory składają się wyłącznie z małych liter alfabetu angielskiego.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać szukany identyfikator J albo słowo BRAK jeżeli taki identyfikator nie istnieje.

Przykład

Wejście:

3
a d
b d
aa zy

Wyjście:

BRAK
c
mz

Wyjaśnienie do przykładu:

W pierwszym zestawie danych pomiędzy identyfikatorami a i d w porządku leksykograficznym mamy dwa identyfikatory b i c. Możliwe jest zatem wyznaczenie identyfikatora spełniającego nierówności D < J < M. Niestety zarówno b jak i c nie spełnią drugiego warunku dotyczącego równej liczby identyfikatorów. W pozostałych dwóch przypadkach wyznaczenie identyfikatora J jest możliwe.