{"problem":{"name":"H. Подземелье","description":{"content":"После прохождения пещеры со сталактитами и сталагмитами дрона Петра принимают на работу в исторический музей, и его основной обязанностью становится поиск кладов. На очередное задание Петра отправляют","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10096H"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nПервая строка содержит целые числа 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) — координаты соответствующего сундука, а также количество золота, находящегося в нём.Гарантируется, что порталы и сундуки находятся только в свободных ячейках.\n\n## Выходные Данные\n\nЕсли дрон может выбраться из пещеры живым, в первой строке выведите «possible», а во второй — максимальное количество золота, которое он может собрать.Если же ему суждено вечно жить в пещере, выведите единственное слово «impossible».\n\n## Примеры\n\nВходные данные4 41 1 2 1...#.#.#.##.#...21 14 441 1 101 2 144 3 64 4 7Выходные данныеpossible37Входные данные2 21 1 2 2.##.00Выходные данныеimpossible\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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`.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10096H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}