Задача №113266. Матрица
Матрица "— это прямоугольная таблица символов. Квадратной матрицей называется матрица с равным количеством строк и столбцов. Квадратная матрица называется симметричной, если её символы симметричны относительно главной диагонали (то есть Mij = Mji для любых i и j).
По данному множеству используемых символов вам необходимо вывести подмножество столбцов минимальной лексикографически симметричной матрицы, которая может быть сформирована, используя все данные символы. Если такой матрицы не существует, то необходимо вывести «IMPOSSIBLE».
Чтобы определить, какая матрица лексикографически меньше, необходимо сравнить их элементы в порядке возрастания номеров рядов (как если бы вы их сравнивали конкатенации их рядов). Меньше та матрица, у которой первый элемент, где нашлось отличие, меньше.
На первой строке стандартного ввода будут заданы числа N (1 ≤ N ≤ 30 000) и K (1 ≤ K ≤ 26) "— соответственно, размер матрицы и количество различных букв, которые встречаются. Далее каждая из K строк содержит заглавную латинскую букву и целое положительное число, разделённые пробелом. Число означает, сколько раз эта буква должна быть использована. Например, если сказано «A 3», это означает, что буква A должна появиться в матрице ровно три раза. Общее количество букв будет ровно N2. Ни одна буква не появится во входном файле дважды.
Следующая строка содержит целое число P (1 ≤ P ≤ 50) "— количество столбцов, которые необходимо вывести. В следующей строке даны сами номера столбцов. Они находятся между 1 и N включительно, заданы в возрастающем порядке и без повторений.
Если возможно построить симметричную матрицу из заданного набора букв, то выведите требуемые столбцы на N строках по P символов без пробелов. Иначе выведите «IMPOSSIBLE» (без кавычек).
Тесты, в которых N не будет превышать 300, будут оценены исходя из 60 баллов.
Тесты, в которых N не будет превышать 3000, будут оценены исходя из 80 баллов.
3 3
A 3
B 2
C 4
3
1 2 3
AAB
ACC
BCC
4 4
A 4
B 4
C 4
D 4
4
1 2 3 4
AABB
AACC
BCDD
BCDD
4 5
E 4
A 3
B 3
C 3
D 3
2
2 4
AC
BE
DE
ED
4 6
F 1
E 3
A 3
B 3
C 3
D 3
4
1 2 3 4
IMPOSSIBLE
3 3 A 3 B 2 C 4 3 1 2 3
AAB ACC BCC
4 4 A 4 B 4 C 4 D 4 4 1 2 3 4
AABB AACC BCDD BCDD
4 5 E 4 A 3 B 3 C 3 D 3 2 2 4
AC BE DE ED
4 6 F 1 E 3 A 3 B 3 C 3 D 3 4 1 2 3 4
IMPOSSIBLE