Иван Фёдорович сыщик с очень большим стажем. Однажды в городе произошла серия больших ограблений. На местах ограбления не было обнаружено ни улик, ни зацепок. Однажды грабителей практически застали врасплох, но они смогли скрыться. На месте преступления Иван Фёдорович заметил, что грабители обронили папку с листком и набором картонных карточек, с вырезанными окошками на этих картах. Придя в офис и рассмотрев улики подробнее, было замечено, что на листке напечатана прямоугольная матрица, состоящая из цифр, а карточки все были размером с матрицу, притом отверстия, вырезанные в карточках, отображали какие-то случайные цифры из матрицы.
Иван Фёдорович вспомнил, что когда-то сталкивался с подобной схемой обозначения мест ограбления, что карточки помогали определить координаты следующего места ограбления. Потому Иван Фёдорович решил выписать координаты всех мест преступлений в виде долготы и широты, а далее найти карточки, которые соответствуют координатам следующих мест преступлений.
Помогите ему быстрее найти преступников, определив координаты следующих мест преступлений.
Координаты преступления собираются при помощи карточки следующим образом:
- на матрицу накладывается карточка;
- далее двигаясь по каждой строке по порядку слева-направо, выписываются цифры, которые попали в прорези;
- цифр всегда 18, притом координаты всегда состоят из 8цифр (две целой части, шесть вещественной), значит два символа игнорируются и обозначают точку в вещественном числе в соответствующем порядке.
Пример матрицы и карточки (где белые участки – это вырезы (отверстия)).
Таким образом начинаем выписывать цифры по строкам слева-направо: 554755831378617673. Знаем, что цифр обозначающих координату 8, а две лишние – обозначающие запятые, получим координаты 55.755831 37.617673.
Также на каждой карточке Иван Фёдорович заметил на углу пометку, которая, как позднее он понял, определяет, как должна быть развёрнута карточка, так как метка должна при наложении всегда находиться в левом верхнем углу при взгляде на неё:
- 1 – метка в левом верхнем углу карточки;
- 2 – метка в правом верхнем углу карточки;
- 3 – метка в правом нижнем углу карточки;
- 4 – метка в левом нижнем углу карточки.
Входные данные
на первой строке подаётся целое число K (2 <= K <= 100) – количество преступлений, которые совершили грабители;
далее на K строках подаются координаты предыдущих мест преступлений в виде вещественных чисел с точкой, разделённых пробелом (например, 55.755831 37.617673)
на следующей строке подаются размеры матрицы и карточек в виде целых чисел N, M (5 <= N,M <= 1000), где N – количество строк матрицы, а M – количество столбцов;
далее на N строках подаются по M цифр матрицы;
после подаётся на новой строке целое число – количество карточек L (K < L <= 100);
далее подаётся на одной строке L цифр от 1 до 4 через пробел, которые отображаются метки карточка в соответствии с порядком их появления;
затем L раз по N строк и M цифр подаются карточки по порядку их появления, которые содержат либо цифру 1 – обозначающую наличие прорези на ней, либо 0 – если прорези в этом месте на карточке нет.
Выходные данные
выведите все координаты будущих мест преступлений (каждую с новой строки), отсортировав их по возрастанию (если две координаты одинаковые по первой координате, то сортировать по возрастанию по второй), координаты одного места выводить через пробел.
Примечание:
·при выводе дробной части координат выводить всегда 6 знаков, если знаков меньше, то дополнять их незначащими нулями;
·если матрица прямоугольная, то гарантируется, что при совмещении метки на карточке с левым верхним углом матрицы, карточка совпадёт с размером матрицы;
·данные на карточках нельзя отзеркаливать (переворачиватькарточки не в плоскости OXY);
·гарантируется, что если даны метки на карточках, то при повороте карточка совпадёт с размером матрицы, не будет такого, что карточка будет иного размера, чем матрица.