I. Двоичная сортировка 2 @ [Онлайн] ICPC Ural Regional Contest Qualifier 2026 @ Timus Online Judge

I. Двоичная сортировка 2

Ограничение времени: 5.0 секунды
Ограничение памяти: 256 МБ

Тимофей прошёл курс по алгоритмам и изучил много разных видов сортировок. Он до сих пор встречает новые и необычные алгоритмы сортировки. Каждый раз, когда Тимофей изучает новую сортировку, ему нужно потренироваться на бинарной строке. Обычно во время тренировки он выбирает последовательность подстрок и сортирует их одну за другой, но иногда эта последовательность получается очень большой, и Тимофей не может потренироваться на длинных строках. Тимофей решил ускорить этот процесс, делая некоторые операции параллельно, и узнал о следующем способе сортировки. В нём используется система из N параллельных конвейеров длины M, пронумерованных сверху вниз от 1 до N, на каждый из которых подаётся по одному биту.

====================================
\| \|	===
====================================	\|
\| \| \|	===
====================================	\|
\|	===
====================================
Система из 4 конвейеров	Недопустимое расположение перемычек

Символами = обозначены конвейеры, а символами | — перемычки, которые соединяют соседние конвейеры. Две перемычки, касающиеся одного конвейера, не могут находиться в одном столбце. Все N битов одновременно едут по конвейерам слева направо с одинаковой скоростью. Когда биты подъезжают к перемычке, она сортирует их. То есть меньший бит идёт на верхний конвейер, а больший — на нижний. Например:

=1=		=0=	=0=		=0=
\|	⟶	\|	\|	⟶	\|
=0=		=1=	=1=		=1=

Система принимает бинарную строку длины N, где i-й бит подаётся на i-й конвейер. Биты едут до конца конвейеров, после чего тоже получается бинарная строка длины N. У Тимофея есть Q бинарных строк длины N, на которых он собирался потренироваться. Помогите для каждой строки определить, какая строка получится на выходе системы.

Исходные данные

В первой строке даны три целых числа N, M, Q (1 ≤ N, M, Q ≤ 3000) — количество конвейеров, длина конвейеров и количество бинарных строк Тимофея.

Со второй по 2 · N-ю строку входных данных находится система конвейеров. В чётных по номеру строках находятся конвейеры, каждый из которых состоит из M символов =, а строки с нечётными номерами состоят из M символов | и пробелов. В одном столбце нет двух перемычек, касающихся одного и того же конвейера.

В следующих Q строках даны бинарные строки длины N, которые Тимофей хочет пропустить через систему.

Результат

Выведите Q бинарных строк, получившихся после прохождения через систему.

Примеры

исходные данные	результат
4 36 4 ==================================== \| \| ==================================== \| \| \| ==================================== \| ==================================== 0110 1000 1011 0111	0011 0010 0111 0111
2 3 2 === \| === 10 01	01 01
5 32 6 ================================ \| \| \|\| ================================ \| \| \| ================================ \| \| \| ================================ \| \| ================================ 10000 11000 11100 11110 10101 01101	00001 00101 01101 01111 00111 00111
4 4 3 ==== \| \| ==== \| \| ==== \| \| ==== 0101 1000 1101	0011 0001 0111

Автор задачи: Тимофей Имаев
Источник задачи: Квалификационный тур Уральского регионального чемпионата ICPC 2026