После прохождения пещеры со сталактитами и сталагмитами дрона Петра принимают на работу в исторический музей, и его основной обязанностью становится поиск кладов. На очередное задание Петра отправляют в подземелье, созданное древней высокоразвитой цивилизацией.
Подземелье представляет собой прямоугольник из 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».
## Входные Данные
Первая строка содержит целые числа 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 41 1 2 1...#.#.#.##.#...21 14 441 1 101 2 144 3 64 4 7Выходные данныеpossible37Входные данные2 21 1 2 2.##.00Выходные данныеimpossible
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of lamps, labeled $ \{1, 2, \dots, n\} $.
Let $ G = (V, E) $ be a dynamic graph where $ V = \{1, 2, \dots, n\} $ and $ E \subseteq \binom{V}{2} $ is the set of currently connected wires. Initially, $ E = \emptyset $.
**Operations**
Process a sequence of $ q \leq 300{,}000 $ queries, each of one of three types:
1. `+ u v`: Add edge $ \{u, v\} $ to $ E $, where $ u \ne v $.
2. `- u v`: Remove edge $ \{u, v\} $ from $ E $, where $ \{u, v\} \in E $.
3. `? u v`: Query whether vertices $ u $ and $ v $ are in the same connected component of $ G $.
**Constraints**
- $ 1 \leq n \leq 100{,}000 $
- Each possible edge is added and removed exactly once.
- All operations respect the garland’s structure (i.e., no invalid edge operations).
**Objective**
For each query of type `? u v`, output `YES` if $ u $ and $ v $ are connected in $ G $, otherwise output `NO`.