D - Logical Filling Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

., o, ? のみからなる長さ N の文字列 S が与えられます。 全ての ? をそれぞれ . または o で置き換えて得られる文字列のうち、以下の条件を全て満たすものの集合を X とします。

  • o の個数がちょうど K個
  • o が連続しない

X が空集合でないことは保証されます。

以下を満たす、長さ N の文字列 T を出力して下さい。ここで、T の左から i 番目の文字を T_i と表記します。

  • X に含まれる全ての文字列の i 文字目が . である場合： T_i= .
  • X に含まれる全ての文字列の i 文字目が o である場合： T_i= o
  • i 文字目が . である文字列も o である文字列も X に含まれている場合： T_i=?

制約

  • 1\leq N\leq 2\times 10^5
  • 0\leq K
  • S は ., o, ? のみからなる長さ N の文字列
  • X は空集合ではない
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

答えを出力せよ。

入力例 1

4 2
o???

出力例 1

o.??

o.o. と o..o の二つの文字列から X はなります。

X に含まれる全ての文字列の 1 文字目は o なので、 T_1 は o です。

X に含まれる全ての文字列の 2 文字目は . なので、 T_2 は . です。

X に含まれる文字列の 3 文字目としては . も o も考えられるので、 T_3 は ? です。

入力例 2

5 2
?????

出力例 2

?????

入力例 3

7 3
.o???o.

出力例 3

.o.o.o.

Score : 400 points

Problem Statement

You are given a string S of length N consisting of the characters ., o, and ?. Among the strings that can be obtained by replacing every ? in S independently with either . or o, let X be the set of strings that satisfy all of the following conditions:

  • The number of os is exactly K.
  • No two os are adjacent.

It is guaranteed that X is non‑empty.

Print a string T of length N that satisfies the following (let T_i denote the i‑th character of T):

  • If the i‑th character of every string in X is ., then T_i= ..
  • If the i‑th character of every string in X is o, then T_i= o.
  • If X contains both a string whose i‑th character is . and a string whose i‑th character is o, then T_i= ?.

Constraints

  • 1 \le N \le 2 \times 10^{5}
  • 0 \le K
  • S is a string of length N consisting of ., o, ?.
  • X is non‑empty.
  • All given numerical values are integers.

Input

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

N K
S

Output

Print the answer.

Sample Input 1

4 2
o???

Sample Output 1

o.??

The set X consists of the two strings o.o. and o..o.

  • The 1st character of every string in X is o, so T_1 is o.
  • The 2nd character of every string in X is ., so T_2 is ..
  • The 3rd character of a string in X can be either . or o, so T_3 is ?.

Sample Input 2

5 2
?????

Sample Output 2

?????

Sample Input 3

7 3
.o???o.

Sample Output 3

.o.o.o.