Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_21_10 - Słowa

Jaś znalazł ostatnio na ulicy dwa długie słowa. Oba te słowa miały długość n liter i były za długie jak na gust naszego bohatera. Jaś postanowił je skrócić i trochę się przy tym zabawić, wymyślił więc dość nietypowy sposób skrócenia tych słów. Chłopiec wypisał sobie pary liczb a i b (ab) i teraz po kolei sprawdza, czy w pierwszym słowie podsłowo zaczynające się na indeksie a i kończące na indeksie b jest identyczne jak podsłowo zaczynające się i kończące na tych samych indeksach w słowie drugim. Jeśli podsłowa są identyczne, to Jaś w obu słowach zmienia najbliższe litery znajdujące się na lewo od pozycji a (o ile takie litery istnieją) na znak # i przechodzi do kolejnej pary liczb. Znak # oczywiście nie jest uznawany za literę. Jeśli podsłowa są różne to Jaś od razu przechodzi do następnej pary liczb.

Po przeanalizowaniu wszystkich par liczb, Jaś wypisał sobie oba słowa bez znaków #. Teraz zastanawia się, czy przypadkiem gdzieś się nie pomylił? Pomóż Jasiowi i napisz program, który dla danych słów, oraz par liczb wyznaczy wynikowe słowa.

Wejście

W pierwszych dwóch liniach wejścia znajdują się słowa, które znalazł Jaś. Każde z nich umieszczone jest w osobnej linii i składa się z n ∈ [1;106] małych liter alfabetu łacińskiego. Słowa indeksowane są od 0. W trzeciej linii wejścia znajduje się liczba m ∈ [1;106] oznaczająca ilość par liczb do przeanalizowania. W każdej z kolejnych m linii znajdują się dwie liczby całkowite a ∈ [0;n) i b ∈ [a;n) opisane w treści zadania.

Wyjście

Na wyjściu należy wypisać wynikowe słowa, w takiej samej kolejności w jakiej zostały wczytane albo -1 jeżeli słowa te są puste.

Przykład

Wejście:

abddqwez
wbdceweq
5
0 1
1 2
5 6
5 5
1 6

Wyjście:

bdwez
bdweq

Wyjaśnienie do przykładu:

Oto jak wyglądają słowa po kolejnych przeanalizowanych parach liczb:

  1. abddqwez
    wbdceweq
  2. #bddqwez
    #bdceweq
  3. #bdd#wez
    #bdc#weq
  4. #bd##wez
    #bd##weq
  5. #bd##wez
    #bd##weq

Dodane przez:Bartek
Data dodania:2015-03-06
Limit czasu wykonania programu:3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.