У Ashish есть бинарная строка \(s\) длины \(n\), которую он хочет отсортировать в неубывающем порядке.
Он может выполнять следующую операцию:
- Выберите подпоследовательность любой длины, элементы которой идут в невозрастающем порядке. Формально, выберите любое \(k\) такое, что \(1 \leq k \leq n\) и любую последовательность \(k\) индексов \(1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n\) такую, что \(s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}\).
- Затем, «разверните» эту последовательность. Формально, поменяйте местами \(s_{i_1}\) с \(s_{i_k}\), \(s_{i_2}\) с \(s_{i_{k-1}}\), \(\ldots\) и \(s_{i_{\lfloor k/2 \rfloor}}\) с \(s_{i_{\lceil k/2 \rceil + 1}}\) (Здесь \(\lfloor x \rfloor\) обозначает наибольшее целое число, не превосходящее \(x\), а \(\lceil x \rceil\) обозначает наименьшее целое число, не меньшее \(x\)).
Найдите минимальное количество операций, необходимых для того, чтобы отсортировать строку в неубывающем порядке. Можно доказать, что всегда можно отсортировать заданную бинарную строку не более чем за \(n\) операций.
Выходные данные
Для каждого набора входных данных выведите следующее:
- минимальное количество операций \(m\) в первой строке (\(0 \le m \le n\)).
- Каждая из следующих \(m\) строк должна иметь вид: \(k\) \(i_1\) \(i_2\) ... \(i_{k}\), где \(k\) — длина, а \(i_1 \lt i_2 \lt ... \lt i_{k}\) — индексы выбранной подпоследовательности. Для них должны выполняться ограничения из условия.
Примечание
В первом наборе входных данных строка уже отсортирована в неубывающем порядке.
Во втором наборе входных данных мы можем выполнить следующую операцию:
В третьем наборе входных данных мы можем выполнить следующую операцию:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7
0011111
5
10100
6
001000
|
0
1
4 1 3 4 5
1
3 3 5 6
|