После прохождения пещеры со сталактитами и сталагмитами дрона Петра принимают на работу в исторический музей, и его основной обязанностью становится поиск кладов. На очередное задание Петра отправляют в подземелье, созданное древней высокоразвитой цивилизацией.
Подземелье представляет собой прямоугольник из N строк и M столбцов, содержащий N × M ячеек. Каждая ячейка либо является свободным квадратом, в котором можно перемещаться, либо монолитным. В свободных ячейках могут находиться сундуки с определённым количеством золота, но не более одного сундука в ячейке. Также в свободных ячейках могут находиться порталы, но не более одного портала в ячейке. В ячейке могут находиться и сундук, и портал одновременно.
Из ячейки, в которой находится портал, можно перемещаться в любую другую ячейку подземелья, если она не является монолитной; пользоваться одним и тем же порталом можно несколько раз. Также дрон может свободно перемещаться по пустым ячейкам, если они являются соседними по горизонтали или вертикали.
Изначально Пётр находится в ячейке (Si; Sj), и затем он некоторое время путешествует, собирает деньги из сундуков, прыгает по порталам и вообще весело проводит время. Однако рано или поздно Пётр должен вернуться домой, а сделать это он может только с помощью специального портала, расположенного в точке (Ei; Ej). Этот портал предназначен только для телепортации на поверхность земли. Точки входа (Si; Sj) и выхода (Ei; Ej) различны, а также могут содержать сундук или обычный портал (или и то, и другое).
Ваша задача — выяснить, может ли Пётр выбраться, и если может, то какое максимальное количество золота он может забрать с собой.
Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 200) — размеры подземелья.
Вторая строка содержит целые числа Si, Sj, Ei, Ej (1 ≤ Si, Ei ≤ N, 1 ≤ Sj, Ej ≤ M) — координаты начальной точки и точки с порталом наружу.
Следующие N строк описывают карту подземелья. Каждая из них содержит M символов '.' или '#', обозначающих соответственно свободные и монолитные ячейки. Следующая строка содержит целое число P (0 ≤ P ≤ N·M) — количество порталов.
Следующие P строк описывают порталы. Каждая из них содержит целые числа Pi и Pj (1 ≤ Pi ≤ N, 1 ≤ Pj ≤ M) — координаты соответствующего портала.
Следующая строка содержит целое число G (0 ≤ G ≤ N·M) — количество сундуков с золотом.
Следующие G строк описывают сундуки. Каждая из них содержит целые числа Gi, Gj, Gc (1 ≤ Gi ≤ N, 1 ≤ Gj ≤ M, 1 ≤ Gc ≤ 109) — координаты соответствующего сундука, а также количество золота, находящегося в нём.
Гарантируется, что порталы и сундуки находятся только в свободных ячейках.
Если дрон может выбраться из пещеры живым, в первой строке выведите «possible», а во второй — максимальное количество золота, которое он может собрать.
Если же ему суждено вечно жить в пещере, выведите единственное слово «impossible».
4 4
1 1 2 1
...#
.#.#
.##.
#...
2
1 1
4 4
4
1 1 10
1 2 14
4 3 6
4 4 7
possible
37
2 2
1 1 2 2
.#
#.
0
0
impossible
