B. Scientific Hypotheses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Termitov is studying $$$n$$$ new hypotheses in the scientific world.

It is known that the $$$i$$$-th hypothesis has an impossibility index $$$p_i$$$. The professor will believe in a hypothesis that is sufficiently plausible but will refuse to believe in one that seems completely fantastic.

Whether the professor believes in the $$$i$$$-th hypothesis depends on his level of imagination $$$f_{i - 1}$$$:

  • If $$$p_i \le f_{i - 1} + c$$$, then the professor believes in the hypothesis ($$$c$$$ is the trust credit parameter).

    In this case, his level of imagination will become $$$f_{i} = \max{(f_{i - 1}, p_i)}$$$.

  • If $$$p_i \gt f_{i - 1} + c$$$, then the professor does not believe in the hypothesis.

    In this case, his level of imagination will become $$$f_{i} = f_{i - 1} - \max{(d, p_i - f_{i - 1} - c)}$$$, where $$$d$$$ is the disappointment degree parameter.

It is also known that none of the values $$$f_0 \dots f_n$$$ can be negative.

You happened to witness this process through a laboratory window. In the end, you saw all the reactions of your colleague $$$r_i$$$ (believed / did not believe), but you did not hear the hypotheses themselves.

Now you are interested in finding any set $$$p_i$$$ that leads to the given sequence of reactions $$$r_i$$$ (considering the constraints on $$$f_i$$$).

If there are multiple suitable sets, output any set with the minimally possible $$$\max{(p_i)}$$$.

Input

The first line contains integers $$$n$$$, $$$f_0$$$, $$$c$$$, $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le f_0, \, c, \, d \le 5000)$$$ — the number of hypotheses, the initial value of the professor's level of imagination, and the parameters of trust credit and disappointment degree, respectively.

The second line contains a string $$$r$$$ $$$(|r| = n; r_i \in [T, F])$$$ — the professor's reactions to the $$$i$$$-th hypothesis.

If $$$r_i = T$$$, then the professor believed in the $$$i$$$-th hypothesis; if $$$r_i = F$$$, then the $$$i$$$-th hypothesis was deemed too implausible.

Output

In the first line, output YES if the sequence $$$p$$$ can be constructed, and NO if such a sequence does not exist.

If the sequence exists, output two more lines.

In the second line, output an integer $$$pmax$$$ — the maximum value among all values $$$p_i$$$.

In the third line, output $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ $$$(0 \le p_i \le pmax)$$$ — suitable values of the impossibility indices.

Examples
Input
5 3 2 1
TFFTT
Output
YES
6
1 6 5 2 0
Input
3 4 1 2
FFF
Output
NO
Note

First test example

Let's show how the given set $$$p_i$$$ leads to the specified set of reactions.

  • $$$p_1 \le f_0 + c$$$ ($$$1 \le 3 + 2$$$), so the professor believed in hypothesis $$$1$$$.

    His imagination remained equal to $$$f_1 = \max{(3, 1)} = 3$$$.

  • $$$p_2 \gt f_1 + c$$$ ($$$6 \gt 3 + 2$$$), so the professor did not believe in hypothesis $$$2$$$.

    His imagination became $$$f_2 = 3 - \max{(1, 6 - 3 - 2)} = 3 - 1 = 2$$$.

  • $$$p_3 \gt f_2 + c$$$ ($$$5 \gt 2 + 2$$$), so the professor did not believe in hypothesis $$$3$$$.

    His imagination became $$$f_3 = 2 - \max{(1, 5 - 2 - 2)} = 2 - 1 = 1$$$.

  • $$$p_4 \le f_3 + c$$$ ($$$2 \le 1 + 2$$$), so the professor believed in hypothesis $$$4$$$.

    His imagination became $$$f_4 = \max{(1, 2)} = 2$$$.

  • $$$p_5 \le f_4 + c$$$ ($$$0 \le 2 + 2$$$), so the professor believed in hypothesis $$$5$$$.

    His imagination became $$$f_5 = \max{(2, 0)} = 2$$$.

It can be shown that it is impossible to construct a set with $$$pmax \lt 6$$$ — this is the smallest value at which $$$r_2 = F$$$.

Also, note that the set provided in the answer is not the only possible one.

For example, the following sets are also among the possible answers to the problem:

  • $$$[3, 6, 5, 0, 2]$$$;
  • $$$[0, 6, 5, 3, 1]$$$;
  • etc.

Second test example

  • $$$r_1 = F$$$, which means $$$p_1 \gt f_0 + c$$$ ($$$p_1 \gt 4 + 1$$$).

    The $$$p_1$$$ that leads to the smallest decrease in imagination is $$$6$$$ or $$$7$$$.

    In this case, $$$f_1 = 4 - \max{(2, 6 - 4 - 1)} = 4 - 2 = 2$$$.

  • $$$r_2 = F$$$, which means $$$p_2 \gt f_1 + c$$$ ($$$p_2 \gt 2 + 1$$$).

    The $$$p_2$$$ that leads to the smallest decrease in imagination is $$$4$$$ or $$$5$$$.

    In this case, $$$f_2 = 2 - \max{(2, 5 - 2 - 1)} = 2 - 2 = 0$$$.

  • $$$r_3 = F$$$, which means $$$p_3 \gt f_2 + c$$$ ($$$p_3 \gt 0 + 1$$$).

    The $$$p_3$$$ that leads to the smallest decrease in imagination is $$$2$$$ or $$$3$$$.

    In this case, $$$f_3 = 0 - \max{(2, 2 - 0 - 1)} = 0 - 2 = -2$$$.

At each step, we tried to minimize the decrease in the level of imagination, but still ended up with a negative value.

This indicates that there is no set $$$p$$$ that leads to the given sequence of reactions.