У вас есть \(n\) цветных кубиков, \(i\)-й кубик имеет цвет \(a_i\).
Вам надо разложить все кубики по полкам. Всего есть \(m\) полок, \(i\)-я из которых вмещает \(s_i\) кубиков. Также, \(s_1 + s_2 + \ldots + s_m = n\).
Допустим, на полке размера \(k\) лежат, в этом порядке, кубики цветов \(c_1, c_2, \ldots, c_k\). Тогда определим разноцветность полки как минимальное расстояние между двумя разными кубиками одного цвета, лежащими на полке, а если все кубики на полке имеют различные цвета, то разноцветность считается равной размеру полки, то есть числу \(k\).
Более формально, разноцветность \(c_1, c_2, \ldots, c_k\) определяется следующим образом:
- Если все цвета \(c_1, c_2, \ldots, c_k\) различны, разноцветность считается равной \(k\);
- Иначе разноцветность определяется как минимальное целое число \(x \geq 1\), для которого найдётся индекс \(i\) \((1 \le i \le k - x)\) такой, что \(c_i = c_{i+x}\).
Для каждой полки вам задана минимальная необходимая разноцветность, то есть вам даны числа \(d_1, d_2, \ldots, d_m\), означающие, что необходимо, чтобы полка \(i\) имела разноцветность \(\geq d_i\) для всех \(i\).
Распределите имеющиеся кубики по полкам, чтобы обеспечить необходимую разноцветность, или сообщите, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите \(-1\), если невозможно распределить кубики по полкам, выполнив все требования. Иначе, выведите \(m\) строк, \(i\)-я из которых содержит \(s_i\) чисел — цвета кубиков, лежащих на \(i\)-й полке, в подходящем порядке.