15. Yandex Cells

Команда Яндекс.devtools разрабатывает редактор таблиц. Вам поручили написать модуль, обрабатывающий запросы объединения и разделения ячеек.

Таблица состоит из $row$ строк, пронумерованных от $1$ до $row$, и $col$ столбцов, пронумерованных от $1$ до $col$. Назовём \textit{элементарной ячейкой} область таблицы, находящуюся на пересечении некоторой строки и некоторого столбца. Каждая элементарная ячейка однозначно задаётся парой координат $(x, y)$, где $x$ — номер строки, в которой находится элементарная ячейка, а $y$ — номер столбца, в которой находится элементарная ячейка. В каждый момент времени таблица разбита на непересекающиеся \textit{ячейки}. Ячейкой является непустая прямоугольная область таблицы, образованная объединением некоторого множества элементарных ячеек. Более формально любая ячейка задаётся четвёркой чисел $(l_x, r_x, l_y, r_y)$ и состоит из объединения всех элементарных ячеек с координатами $(x, y)$ такими, что $l_x \leq x \leq r_x$ и $l_y \leq y \leq r_y$.

Для удобства работы с таблицами для каждой таблицы существует её ASCII-представление. ASCII-представление таблицы состоит из символов -, |, + и пробела. Для каждой строки фиксируется высота $h_i$, а для каждого столбца фиксируется ширина $w_i$. ASCII-представлением таблицы является матрица из символов с $m_{row} = (\sum_{i = 1}^{row} h_i) + row + 1$ строками, пронумерованными от $1$ до $m_{row}$, и $m_{col} = (\sum_{i = 1}^{col} w_i) + col + 1$ столбцами, пронумерованными от $1$ до $m_{col}$. Ячейке, заданной четвёркой чисел $l_x, r_x, l_y, r_y$, соответствует подматрица матрицы символов, состоящая из символов с координатами $(p, q)$ такими, что $(\sum_{i = 1}^{l_x - 1} h_i) + l_x + 1 \leq p \leq (\sum_{i = 1}^{r_x} h_i) + r_x$ и $(\sum_{i = 1}^{l_y - 1} w_i) + l_y + 1 \leq q \leq (\sum_{i = 1}^{r_y} w_i) + r_y$.

Назовём элемент матрицы с координатами $(p, q)$ горизонтальным разделителем, если выполнено одно из следующих условий:

• Хотя бы один из элементов $(p, q - 1)$, $(p, q + 1)$ не существует (то есть $q - 1 = 0$ или $q + 1 = m_{col} + 1$).
• Элементы $(p, q - 1)$ и $(p, q + 1)$ существуют и принадлежат различным ячейкам.

Назовём элемент матрицы с координатами $(p, q)$ вертикальным разделителем, если выполнено одно из следующих условий:

• Хотя бы один из элементов $(p - 1, q)$, $(p + 1, q)$ не существует (то есть $p - 1 = 0$ или $p + 1 = m_{row} + 1$).
• Элементы $(p - 1, q)$ и $(p + 1, q)$ существуют и принадлежат различным ячейкам.

Назовём элемент матрицы с координатами $(p, q)$ \textit{крестообразным разделителем}, если он не принадлежит ни одной ячейке и среди четырёх элементов $(p - 1, q)$, $(p, q - 1)$, $(p + 1, q)$ и $(p, q + 1)$ найдётся хотя бы один горизонтальный и вертикальный разделитель.

Символ, соответствующий элементу матрицы с координатами $(p, q)$, определяется следующими правилами:

• Если элемент матрицы принадлежит некоторой ячейке, то он обозначается пробелом.
• Если элемент матрицы является горизонтальным разделителем, но не является крестообразным разделителем, то он обозначается символом |.
• Если элемент матрицы является вертикальным разделителем, но не является крестообразным разделителем, то он обозначается символом -.
• Если элемент матрицы является крестообразным разделителем, то он обозначается символом +.

На вход модуль принимает ASCII-описание таблицы. Некоторые клетки уже могут быть объединены.

Затем к модулю поступает $q$ запросов одного из двух типов:

• split pos — разделить объединенную ячейку, содержащую элементарную ячейку с координатой pos на элементарные ячейки.

  • Если ячейка с координатой pos элементарная, то модуль должен вывести Can not split elementary cell
  • Иначе модуль должен разделить данную ячейку на элементарные и вывести Split onto NUM cells, где NUM — количество образованных элементарных ячеек.

• merge pos1 pos2 — объединить ячейки, содержащие элементарные ячейки с координатами pos1 и pos2 соответственно

  • Если данные элементарные ячейки содержатся в одной и той же объединенной ячейке, то модуль должен вывести Can not merge cell with itself
  • Иначе если эти объединенные ячейки выровнены горизонтально (левая граница одной ячейки полностью совпадает с правой границей другой ячейки), то модуль должен объединить их и вывести Merged horizontally-aligned cells
  • Иначе если эти объединенные ячейки выровнены вертикально (нижняя граница одной ячейки полностью совпадает с верхней границей другой ячейки), то модуль должен объединить их и вывести Merged vertically-aligned cells
  • Иначе модуль должен вывести Can not merge unaligned cells

После вывода статуса каждого запроса который изменил таблицу модуль должен вывести и полученную таблицу.

Первая строка содержит два целых числа $m_{row}$ и $m_{col}$ ($3 \le m_{row}, m_{col}$; $m_{row} \times m_{col} \le 10^4$) — количество строк и столбцов, задающих ASCII-описание таблицы.

Следующие $m_{row}$ строк содержат по $m_{col}$ символов каждый и задают ASCII-описание таблицы.

Следующая строка содержит целое число $row$ ($1 \le row \le \lfloor\frac{m_{row} - 1}{2}\rfloor$) — количество строк таблицы.

Следующая строка содержит $row$ целых чисел $h_i$ ($1 \le h_i$; $\sum_{i = 1}^{row}{h_i} + row + 1 = m_{row}$) — высоты строк таблицы.

Следующая строка содержит целое число $col$ ($1 \le m \le \lfloor\frac{m_{col} - 1}{2}\rfloor$) — количество столбцов таблицы.

Следующая строка содержит $col$ целых чисел $w_i$ ($1 \le w_i$; $\sum_{i = 1}^{col}{w_i} + col + 1 = m_{col}$) — ширины столбцов таблицы.

Следующая строка содержит целое число $q$ ($1 \le q \le 10^3$) — количество запросов к модулю.

Следующие $q$ строк содержат запросы к модулю в формате, указанном выше.

Координаты ячейки $c$ описываются как $col_crow_c$, где $row_c$ — номер строки ($1 \le row_c \le row$), а $col_c$ — номер столбца, столбцы нумеруются так:

Для каждого запроса выведите его статус и в случае его успешного завершения таблицу, получившуюся в результате применения этого запроса.