Background

HR has just finished a simple and pretty problem, and it wants to try this one. But it is too weak and cannot solve it. Can you help it?

Problem Description

Construct a lowercase letter string of length $n$, such that its similarity with the given lowercase letter string $s$ of length $n$ is within the range $[l,r]$.

Define the similarity of two strings $a,b$ of length $n$ as $\sum^{n}_{i=1}[a_i=b_i]$.

You need to make the constructed string as small as possible in lexicographical order.

Input Format

The first line contains three positive integers $n,l,r$.

The next line contains a string, representing the given lowercase letter string $s$.

Output Format

Output one line containing a string, representing the lexicographically smallest feasible string you construct.

3 1 2
aab

aaa

4 4 4
awoi

awoi

Hint

Constraints

This problem uses bundled tests.

Special Property A: $l=r=n$ or $l=0,r=n$.

Special Property B: Every character of $s$ is a, or every character is not a.

For $100\%$ of the testdata, $1 \leqslant n \leqslant 10^6$, $0 \leqslant l \leqslant r \leqslant n$, and the length of $s$ is $n$.

Staff | $\text{Idea}$ | $\text{Data}$ | $\text{Check}$ | $\text{Solution}$ | | :----------: | :----------: | :----------: | :----------: | | 玄学OIER荷蒻 | QwQ666_666 & 玄学OIER荷蒻 | QwQ666_666| 玄学OIER荷蒻 |

Translated by ChatGPT 5