Price Control in the PIM/PDM

The process of manufacturing digital electronic components in the Industrial/Digital Hub of Manaus (PIM/PDM) is intense, with complex products that can take a day to be fully manufactured. Over the last $N$ days, an AMCC factory in the complex digital electronics industry produced exactly one of these products per day.

With the fluctuation of the dollar, the estimated price of the product produced daily by AMCC also varies, increasing or decreasing. For a certain sales estimate control, it is indicated whether there is a variation from one day to the next, with an increase of 1 unit in the standard price if the value increased and a decrease of 1 unit if the value decreased, this every day. As a standard, for any initial value of the product to have the price variation controlled, if it was more expensive, the letter "A" was recorded, and if it was cheaper, the letter "B" was recorded. On the first day of the control period, no record was made as there was no "previous day" to compare with, that is, the notes began from the second day.

At the end of the $N$ day control period, the factory managers have $N-1$ price variation records. It is observed that the price never goes negative and on at least one of the days it will zero.

Based on the price control strategy of the AMCC company, determine the price of the product on the $N$ days of the evaluation/control period.

Input

The first line contains the integer $N$, representing how many days are in the product's price evaluation/control period. The second line contains a string of size $N-1$, corresponding to the daily records. The first character represents the record made on the second day, the second character the record of the third day, and so on.

Output

The output should consist of a line, containing $N$ integers separated by blank spaces, representing the product's price on each of the $N$ days. It should be respected that * $2 \leq N \leq 10^{6}$.