103802: [Atcoder]ABC380 C - Move Segment

Problem Statement

You are given a string $S$ of length $N$ consisting of 0 and 1.
Move the $K$-th 1-block from the beginning in $S$ to immediately after the $(K-1)$-th 1-block, and print the resulting string.

It is guaranteed that $S$ contains at least $K$ 1-blocks.

Here is a more precise description.

• Let $S_{l\ldots r}$ denote the substring of $S$ from the $l$-th character through the $r$-th character.
• We define a substring $S_{l\ldots r}$ of $S$ to be a 1-block if it satisfies all of the following conditions:
  • $S_l = S_{l+1} = \cdots = S_r = $ 1
  • $l = 1$ or $S_{l-1} = $ 0
  • $r = N$ or $S_{r+1} = $ 0

• Suppose that all 1-blocks in $S$ are $S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}$, where $l_1 < l_2 < \cdots < l_m$.

  Then, we define the length $N$ string $T$, obtained by moving the $K$-th 1-block to immediately after the $(K-1)$-th 1-block, as follows:

  • $T_i = S_i$ for $1 \leq i \leq r_{K-1}$
  • $T_i = $ 1 for $r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1$
  • $T_i = $ 0 for $r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K$
  • $T_i = S_i$ for $r_K + 1 \leq i \leq N$

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $S$ is a string of length $N$ consisting of 0 and 1.
• $2 \leq K$
• $S$ contains at least $K$ 1-blocks.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$S$

Output

Print the answer.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

$S$ has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

问题陈述

给你一个由0和1组成的长度为$N$的字符串$S$。
将字符串$S$中从开头开始的第$K$个1块移动到第$(K-1)$个1块之后，并打印得到的字符串。

保证$S$至少包含$K$个1块。

以下是更精确的描述。

• 令$S_{l\ldots r}$表示从$S$的第$l$个字符到第$r$个字符的子字符串。
• 如果子字符串$S_{l\ldots r}$满足以下所有条件，我们将其定义为1块：
  • $S_l = S_{l+1} = \cdots = S_r = $ 1
  • $l = 1$或者$S_{l-1} = $ 0
  • $r = N$或者$S_{r+1} = $ 0

• 假设$S$中的所有1块是$S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}$，其中$l_1 < l_2 < \cdots < l_m$。

  然后，我们定义长度为$N$的字符串$T$，通过将第$K$个1块移动到第$(K-1)$个1块之后得到，如下所示：

  • $T_i = S_i$ 对于$1 \leq i \leq r_{K-1}$
  • $T_i = $ 1 对于$r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1$
  • $T_i = $ 0 对于$r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K$
  • $T_i = S_i$ 对于$r_K + 1 \leq i \leq N$

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $S$是由0和1组成的长度为$N$的字符串。
• $2 \leq K$
• $S$至少包含$K$个1块。

输入

输入从标准输入以下格式给出：

$N$ $K$
$S$

输出

打印答案。

示例输入1

15 3
010011100011001

示例输出1

010011111000001

$S$有四个1块：从第2个字符到第2个字符，从第5个字符到第7个字符，从第11个字符到第12个字符，以及从第15个字符到第15个字符。

示例输入2

10 2
1011111111

示例输出2

1111111110