Bessie's Interview

Bessie is looking for a new job! Luckily, $K$ farmers are hiring right now and holding interviews. Jobs are very competitive, so the farmers have decided to number the cows in the order they applied and interview them in that order. There are $N$ cows that applied before Bessie, so her number is $N+1$ ($1 \leq K \leq N \leq 3 \cdot 10^5$).

The interview process works as follows. At time $0$, farmer $i$ starts interviewing cow $i$ for each $1 \leq i \leq K$. When a farmer finishes an interview, he immediately starts interviewing the next cow in line. If several farmers finish at the same time, the next cow may be interviewed by any of the available farmers, of her choice.

For each $1 \leq i \leq N$, cow $i$'s interview takes exactly $t_i$ minutes ($1 \leq t_i \leq 10^9$). Bessie knows these values, but she does not know which farmer each cow prefers.

Bessie wants to prepare carefully. She needs to know when her interview begins and which farmers could interview her. Find this information.

The first line contains two integers $N$ and $K$.

The second line contains $N$ integers $t_1 \dots t_N$.

On the first line, print the time at which Bessie's interview begins.

On the second line, print a bit string of length $K$. The $i$-th bit is $1$ if farmer $i$ could interview Bessie, and $0$ otherwise.