Итак, вы решили провести свой раунд на Codeforces. Приготовили задачи: условия, решения, чекеры, валидаторы, тесты... И тут внезапно ваш координатор просит вас заменить все ваши тесты в самой простой задачи на наборы входных данных!
Изначально каждый тест в данной задаче — это просто массив. Максимальный размер массива равен \(k\). Для простоты будем считать, что содержимое массива не важно. У вас есть \(n\) тестов; \(i\)-й тест — это массив размера \(m_i\) (\(1 \le m_i \le k\)).
Ваш координатор просит вас распределить все ваши массивы по нескольким наборам входных данных. Каждый набор может включать в себя несколько массивов. Однако, в каждом наборе входных данных должно быть не больше \(c_1\) массивов размера больше или равного \(1\) (\(\ge 1\)), не больше \(c_2\) массивов размера больше или равного \(2\), \(\dots\), не больше \(c_k\) массивов размера больше или равного \(k\). Также \(c_1 \ge c_2 \ge \dots \ge c_k\).
Теперь ваша задача — составить новые наборы входных данных так, чтобы:
- каждый из изначальных массивов встречается ровно в одном наборе входных данных;
- для каждого набора тестовых данных выполняются приведенные условия;
- количество наборов тестовых данных минимально возможно.
Выведите минимальное количество наборов тестовых данных, которое можно достичь, а также размеры массивов в каждом наборе входных данных.
Выходные данные
В первой строке выведите одно целое число \(ans\) (\(1 \le ans \le n\)) — минимальное количество наборов входных данных, которое можно достичь.
Каждая из следующих \(ans\) строк должна содержать описание набора входных данных в следующем формате:
\(t\) \(a_1\) \(a_2\) \(\dots\) \(a_{t}\) (\(1 \le t\le n\)) — в наборе входных данных содержится \(t\) массивов, \(a_i\) — это размер \(i\)-го массива в этом наборе входных данных.
Каждый из изначальных массивов должен содержаться в ровно одном наборе входных данных. В частности, это подразумевает, что сумма всех значений \(t\) по всем \(ans\) наборам входных данных должна быть равна \(n\).
Обратите внимание, что ответ существует всегда, потому что \(c_k \ge 1\) (а следовательно \(c_1 \ge 1\)).
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере не существует способа распределить все тесты по меньше, чем \(3\), наборам входных данных. Данный ответ удовлетворяет всем условиям: в каждом наборе входных данных не больше \(4\) массивов размера больше или равного \(1\) и не больше \(1\) массива размера больше или равного \(2\) и \(3\).
Обратите внимание, что существует несколько правильных ответов на данный тест. Например, наборы входных данных с размерами \([[2], [1, 2], [3]]\) тоже будут правильными.
Однако, наборы тестовых данных с размерами \([[1, 2], [2, 3]]\) будут неправильными, потому что во втором наборе входных данных есть \(2\) массива размера больше или равного \(2\).
Обратите внимание на разницу между третьим и четвертым примером. В третьем примере можно собрать до \(5\) массивов размера больше или равного \(1\) в набор входных данных, поэтому одного набора достаточно. А в четвертом примере можно иметь не больше \(1\) массива. Поэтому каждый массив приходится выделять в отдельный набор входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2 2 3
4 1 1
|
3
1 2
2 1 3
1 2
|
|
2
|
6 10
5 8 1 10 8 7
6 6 4 4 3 2 2 2 1 1
|
2
3 8 5 7
3 10 8 1
|
|
3
|
5 1
1 1 1 1 1
5
|
1
5 1 1 1 1 1
|
|
4
|
5 1
1 1 1 1 1
1
|
5
1 1
1 1
1 1
1 1
1 1
|