Беси ищет новую работу. К счастью сейчас \(K\) фермеров проводят интервью
для найма работников. Поскольку желающих найти работу много, фермеры
решили перенумеровать коров и интервьюировать их в порядке нумерации.
\(N\) коров подали заявки на интервью, поэтому у Беси номер \(N+1\)
(\(1 \leq K \leq N \leq 3 \cdot 10^5\)).
Процесс интервью проходит следующим образом. В момент времени \(0\)
фермер \(i\) начинает интервью с коровой \(i\) для каждого \(1 \leq i \leq K\).
После того, фермер заканчивает интервью он немедленно начинает
интервьюировать следующую корову по порядку. Если несколько фермеров
закончили интервью в одно и то же время, следующая корова может выбрать
сама к какому из фермеров пойдёт на интервью.
Для каждого \(1\le i\le N\), Беси знает, что интервью коровы \(i\) займёт ровно
\(t_i\) минут (\(1 \leq t_i \leq 10^9\)). Однако она не знает, какого фермера
предпочтёт каждая корова.
Поскольку работа очень важна для Беси, она хочет хорошо подготовиться
к интервью. Чтобы сделать это, она должна знать, когда она попадёт на интервью
и к какому фермеру может потенциально попасть.
Помогите найти эту информацию!
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит два целых числа
\(N\) и
\(K\).
Вторая строка ввода содержит \(N\) целых чисел \(t_1 \dots t_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
На первой строке выведите время, в которое начнётся интервью Беси.
На второй строке выведите битовую строку длины \(K\), где \(i\)-ый бит равен
\(1\) если Беси может попасть на интервью к фермеру \(i\) и \(0\) в противном
случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
3 1 4159 2 6 5
|
8
110
|