Региональная студенческая предметная олимпиада по информатике (предмет) 2017 г.

Соревнование завершилось 09.04.17 в 16:00

C. Таблица символов (150 баллов)

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

На нашей планете существует поле — прямоугольное поле N \times M, — созданное с помощью двух строк, где N — длина первой строки, а M — длина второй. Первая строка идет по горизонтали, вторая — по вертикали.

Задается K правил кодирования “a b c”, где a — символ из первой строки, b — символ из второй строки, c — символ, который будет стоять на пересечении координат символов a и b в поле. Не существует двух правил с одинаковым символом c.

На данный момент государственная задача первостепенной важности — смоделировать такое поле, а также уметь находить ближайший по манхэттенскому расстоянию символ к заданному. По счастливой случайности, эта задача совпадает с вашей.

Входные данные

Первая и вторая строки входных данных содержат две непустые строки, состоящие из латинских строчных и заглавных букв. Длины строк не превосходят 10^6.

В третьей строке входных данных находится целое число K — количество заданных правил кодирования (1 \leqslant K \leqslant 52).

Далее следует K строк, каждая из которых описывает очередное правило кодирования тремя символами через пробел. Гарантируется, что символы представляют собой только строчные или заглавные латинские буквы.

В следующей строке входных данных находится целое число L — количество запросов ближайшего символа (1 \leqslant L \leqslant 10^5).

Далее следует L строк, каждая из которых описывает очередной запрос ближайшего символа двумя целыми числами x_i, y_i — координаты символа в поле, для которого нужно найти ближайший такой же. 1 \leqslant x_i \leqslant N, 1 \leqslant y_i \leqslant M, где N — длина первой строки (в поле идет по горизонтали), M — длина второй (в поле идет по вертикали).

Выходные данные

Для каждого запроса из входных данных в отдельной строке, в порядке следования во входных данных, нужно вывести два целых числа x_j, y_j — координаты ближайшего по манхэттенскому расстоянию такого же символа в поле.

Если существует больше одной удовлетворяющей пары координат, вывести любую. Если на запрашиваемых координатах нет символа, который бы кодировался заданными правилами, то вывести “Not found” (без кавычек). Если же ближайшего такого же символа невозможно найти, то вывести “Nothing” (без кавычек).

Примеры
Стандартный вводСтандартный вывод
abcce
abcdbda
5
c d d
a a a
a b b
d d f
e c y
6
1 2
3 4
1 4
2 2
1 1
5 3
1 5
4 4
Not found
Not found
1 7
Nothing
Пояснения к примерам

Поле из приведенного теста:

image

Примечания

Манхэттенское расстояние — расстояние между двумя точками, равное сумме модулей разностей их координат.