D. String Traversal Paradigm 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of size $$$n$$$ consisting of lowercase English alphabets $$$(a \space to \space z)$$$. The cost of moving from index $$$i$$$ $$$(c_i$$$ is character at index $$$i)$$$ to index $$$j$$$ $$$(c_j$$$ is character at index $$$j)$$$ is as follows:

  1. If $$$c_i \neq c_j$$$, then cost to move from $$$c_i$$$ to $$$c_j$$$ is $$$|i - j|$$$.
  2. If $$$c_i == c_j$$$, then cost to move from $$$c_i$$$ at $$$i$$$ to $$$c_j$$$ at $$$j$$$ is $$$K$$$ .

You are given a starting index $$$V$$$. You need to find minimum cost to move from $$$V$$$ to all other indices.

Input

First line contains $$$n$$$, $$$V$$$ and $$$K$$$. $$$(1 \leq n \leq 10^3)$$$ $$$(0 \leq V \leq n-1)$$$ $$$(1 \leq K \leq 10^3)$$$

Next line contains string $$$s$$$.

Output

Output an array $$$D$$$ of size $$$n$$$ where $$$D_i$$$ denotes minimum cost of reaching index $$$i$$$ from $$$V$$$.

Examples
Input
9 0 1
aabbcedba
Output
0 1 2 3 4 4 3 2 1
Input
18 3 3
ababcacaaabbecbadc
Output
3 2 1 0 1 2 3 4 4 4 3 3 4 4 3 4 5 4
Note

In test case $$$1$$$, the minimum cost to move to index $$$4$$$ from index $$$0$$$ is $$$|4-0| = 4$$$. The minimum cost to move to index $$$5$$$ from index $$$0$$$ is also $$$4$$$. We can move from index $$$0$$$ to index $$$8$$$ at cost of $$$1$$$(as $$$c_0 == c_8$$$, so cost is equal to K i.e $$$1$$$) and then from index $$$8$$$ to index $$$5$$$ at cost of $$$3$$$.