F. Группы скобок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:

  • скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
  • скобочные последовательности «)(», «(» и «)» — неправильные.

Вам даны $$$n$$$ скобочных последовательностей $$$s_1, s_2, \dots, s_n$$$ (не обязательно правильных) и четное целое число $$$k$$$. Ваша задача — разбить их на группы таким образом, чтобы:

  • каждая скобочная последовательность принадлежала ровно одной группе;
  • для каждой группы существовала правильная скобочная последовательность длины ровно $$$k$$$, такая что каждая последовательность скобок, назначенная этой группе, не являлась бы подстрокой этой последовательности.

Какое наименьшее количество групп можно получить? Если это невозможно сделать для любого количества групп, сообщите об этом. В противном случае выведите группы и любую подходящую правильную скобочную последовательность для каждой группы. Если есть несколько ответов с наименьшим количеством групп, выведите любой из них.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 50$$$; $$$2 \le k \le 50$$$; $$$k$$$ четное).

В $$$i$$$-й из следующих $$$n$$$ строк записана скобочная последовательность $$$s_i$$$ ($$$2 \le |s_i| \le k$$$). Она состоит только из символов '(' и ')'.

Выходные данные

Если невозможно разбить все скобочные последовательности на группы в соответствии с правилами, выведите $$$-1$$$.

В противном случае выведите наименьшее возможное количество групп $$$m$$$ в первой строке. Затем должно следовать $$$m$$$ блоков данных:

  • Первая строка каждого блока должна содержать правильную скобочную последовательность длины $$$k$$$.
  • Вторая строка должна содержать одно целое число $$$g$$$ — количество скобочных последовательностей в текущей группе.
  • Третья строка должна содержать $$$g$$$ целых чисел от $$$1$$$ до $$$n$$$ — индексы скобочных последовательностей, принадлежащих текущей группе.

Ни одна из этих скобочных последовательностей не должна быть подстрокой выбранной правильной скобочной последовательности. Каждый индекс от $$$1$$$ до $$$n$$$ должен принадлежать ровно одной группе.

Если есть несколько ответов с наименьшим $$$m$$$, выведите любой из них.

Примеры
Входные данные
3 6
)))
(((
(())
Выходные данные
1
(()())
3
1 2 3
Входные данные
4 6
(()
()(
())
((((((
Выходные данные
2
(())()
1
2
()()()
3
1 4 3
Входные данные
2 6
()
)(
Выходные данные
-1