{"raw_statement":[{"iden":"statement","content":"После прохождения пещеры со сталактитами и сталагмитами дрона Петра принимают на работу в исторический музей, и его основной обязанностью становится поиск кладов. На очередное задание Петра отправляют в подземелье, созданное древней высокоразвитой цивилизацией. \n\nПодземелье представляет собой прямоугольник из N строк и M столбцов, содержащий N × M ячеек. Каждая ячейка либо является свободным квадратом, в котором можно перемещаться, либо монолитным. В свободных ячейках могут находиться сундуки с определённым количеством золота, но не более одного сундука в ячейке. Также в свободных ячейках могут находиться порталы, но не более одного портала в ячейке. В ячейке могут находиться и сундук, и портал одновременно.\n\nИз ячейки, в которой находится портал, можно перемещаться в любую другую ячейку подземелья, если она не является монолитной; пользоваться одним и тем же порталом можно несколько раз. Также дрон может свободно перемещаться по пустым ячейкам, если они являются соседними по горизонтали или вертикали.\n\nИзначально Пётр находится в ячейке (Si; Sj), и затем он некоторое время путешествует, собирает деньги из сундуков, прыгает по порталам и вообще весело проводит время. Однако рано или поздно Пётр должен вернуться домой, а сделать это он может только с помощью специального портала, расположенного в точке (Ei; Ej). Этот портал предназначен только для телепортации на поверхность земли. Точки входа (Si; Sj) и выхода (Ei; Ej) различны, а также могут содержать сундук или обычный портал (или и то, и другое).\n\nВаша задача — выяснить, может ли Пётр выбраться, и если может, то какое максимальное количество золота он может забрать с собой.\n\nПервая строка содержит целые числа N и M (1 ≤ N, M ≤ 200) — размеры подземелья. \n\nВторая строка содержит целые числа Si, Sj, Ei, Ej (1 ≤ Si, Ei ≤ N, 1 ≤ Sj, Ej ≤ M) — координаты начальной точки и точки с порталом наружу.\n\nСледующие N строк описывают карту подземелья. Каждая из них содержит M символов '.' или '#', обозначающих соответственно свободные и монолитные ячейки. Следующая строка содержит целое число P (0 ≤ P ≤ N·M) — количество порталов.\n\nСледующие P строк описывают порталы. Каждая из них содержит целые числа Pi и Pj (1 ≤ Pi ≤ N, 1 ≤ Pj ≤ M) — координаты соответствующего портала. \n\nСледующая строка содержит целое число G (0 ≤ G ≤ N·M) — количество сундуков с золотом.\n\nСледующие G строк описывают сундуки. Каждая из них содержит целые числа Gi, Gj, Gc (1 ≤ Gi ≤ N, 1 ≤ Gj ≤ M, 1 ≤ Gc ≤ 109) — координаты соответствующего сундука, а также количество золота, находящегося в нём.\n\nГарантируется, что порталы и сундуки находятся только в свободных ячейках.\n\nЕсли дрон может выбраться из пещеры живым, в первой строке выведите «possible», а во второй — максимальное количество золота, которое он может собрать.\n\nЕсли же ему суждено вечно жить в пещере, выведите единственное слово «impossible».\n\n"},{"iden":"входные данные","content":"Первая строка содержит целые числа 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) — координаты соответствующего сундука, а также количество золота, находящегося в нём.Гарантируется, что порталы и сундуки находятся только в свободных ячейках."},{"iden":"выходные данные","content":"Если дрон может выбраться из пещеры живым, в первой строке выведите «possible», а во второй — максимальное количество золота, которое он может собрать.Если же ему суждено вечно жить в пещере, выведите единственное слово «impossible»."},{"iden":"примеры","content":"Входные данные4 41 1 2 1...#.#.#.##.#...21 14 441 1 101 2 144 3 64 4 7Выходные данныеpossible37Входные данные2 21 1 2 2.##.00Выходные данныеimpossible"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of lamps, labeled $ \\{1, 2, \\dots, n\\} $.  \nLet $ 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 $.  \n\n**Operations**  \nProcess a sequence of $ q \\leq 300{,}000 $ queries, each of one of three types:  \n1. `+ u v`: Add edge $ \\{u, v\\} $ to $ E $, where $ u \\ne v $.  \n2. `- u v`: Remove edge $ \\{u, v\\} $ from $ E $, where $ \\{u, v\\} \\in E $.  \n3. `? u v`: Query whether vertices $ u $ and $ v $ are in the same connected component of $ G $.  \n\n**Constraints**  \n- $ 1 \\leq n \\leq 100{,}000 $  \n- Each possible edge is added and removed exactly once.  \n- All operations respect the garland’s structure (i.e., no invalid edge operations).  \n\n**Objective**  \nFor each query of type `? u v`, output `YES` if $ u $ and $ v $ are connected in $ G $, otherwise output `NO`.","simple_statement":"You are given n lamps and a series of operations. Initially, no wires are connected. There are three types of operations:\n\n1. `connect a b` — connect lamp a and lamp b with a wire.\n2. `disconnect a b` — remove the wire between lamp a and lamp b.\n3. `test a b` — check if lamp a and lamp b are connected (directly or indirectly) by wires.\n\nAfter each `test` operation, answer \"YES\" if the two lamps are connected, or \"NO\" if they are not.","has_page_source":false}