베시의 면접

베시는 새 일자리를 찾고 있다! 다행히 $K$명의 농부가 지금 사람을 뽑으며 면접을 진행하고 있다. 일자리 경쟁이 매우 치열해서, 농부들은 소가 지원한 순서대로 번호를 매기고 그 순서에 따라 면접을 보기로 했다. 베시보다 먼저 지원한 소가 $N$마리이므로 베시의 번호는 $N+1$이다 ($1 \leq K \leq N \leq 3 \cdot 10^5$).

면접은 다음과 같이 진행된다. 시각 $0$에 각 $1 \leq i \leq K$에 대해 농부 $i$가 소 $i$의 면접을 시작한다. 농부는 면접을 마치면 곧바로 줄에서 다음 소의 면접을 시작한다. 여러 농부가 같은 시각에 면접을 마치면, 다음 소는 자신의 선호에 따라 비어 있는 농부 중 누구에게든 면접을 받을 수 있다.

각 $1 \leq i \leq N$에 대해 소 $i$의 면접은 정확히 $t_i$분이 걸린다 ($1 \leq t_i \leq 10^9$). 베시는 이 값을 알고 있지만, 각 소가 어느 농부를 선호하는지는 알지 못한다.

베시는 면접을 철저히 준비하려 한다. 그러려면 면접이 언제 시작되는지, 그리고 어떤 농부가 베시를 면접할 수 있는지 알아야 한다. 이 정보를 구하라.

첫째 줄에 두 정수 $N$과 $K$가 주어진다.

둘째 줄에 $N$개의 정수 $t_1 \dots t_N$이 주어진다.

첫째 줄에 베시의 면접이 시작되는 시각을 출력한다.

둘째 줄에 길이가 $K$인 비트열을 출력한다. $i$번째 비트는 농부 $i$가 베시를 면접할 수 있으면 $1$, 그렇지 않으면 $0$이다.