31769번 - Bessie's Interview 다국어

문제

Bessie is looking for a new job! Fortunately, $K$ farmers are currently hiring and conducting interviews. Since jobs are highly competitive, the farmers have decided to number and interview cows in the order they applied. 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 will go as follows. At time 0ドル,ドル farmer $i$ will start interviewing cow $i$ for each 1ドル \leq i \leq K$. Once a farmer finishes an interview, he will immediately begin interviewing the next cow in line. If multiple farmers finish at the same time, the next cow may choose to be interviewed by any of the available farmers, according to her preference.

For each 1ドル\le i\le N,ドル Bessie already knows that cow $i$'s interview will take exactly $t_i$ minutes (1ドル \leq t_i \leq 10^9$). However, she doesn't know each cow's preference of farmers.

Since this job is very important to Bessie, she wants to carefully prepare for her interview. To do this, she needs to know when she will be interviewed and which farmers could potentially interview her. Help her find this information!

입력

The first line of the input will contain two integers $N$ and $K$.

The second line will contain $N$ integers $t_1 \dots t_N$.

출력

On the first line, print the time Bessie's interview will begin.

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

제한

힌트