Maximize Coal Production

You are given a sequence of food trucks arriving in order. There are three types of food trucks: Meat truck (M), Fish truck (F) and Bread truck (B). There are two coal mines, each employing a team of miners. When a food truck arrives at a mine, the miners produce coal based on the variety of food types delivered in the last two visits to that mine (or fewer if there have been less than two deliveries) together with the current delivery.

The production rule is as follows for a mine when a new food truck arrives:

• If the new truck and the previous up to two trucks (if available) are all of the same type, the mine produces 1 unit of coal.
• If there are exactly two different types among these trucks, the mine produces 2 units of coal.
• If there are three different types among these trucks, the mine produces 3 units of coal.

You know the sequence and type of the arriving food trucks. Your task is to decide, for each truck (in order), to which mine (1 or 2) it should be assigned so that the total coal production from both mines is maximized. Note that a food truck cannot be split, and the two mines may receive a different number of trucks (even all trucks may be sent to one mine if that maximizes production).

Observation: It turns out that grouping the trucks (i.e. sending them all to the same mine) always yields an optimal or tied optimal outcome. In such a case, the production at the first truck is 1, at the second truck is either 1 (if the same type) or 2 (if different), and for trucks 3 and onward, the production is based on the diversity among the truck types of the previous two deliveries and the current one (which is at most 3). Alternating assignments resets the history and produces only 1 unit per truck. Therefore, an optimal solution is to assign all food trucks to mine 1.

Your program should output a sequence of n numbers (each either 1 or 2) separated by spaces, where the i-th number indicates the mine (1 or 2) to which the i-th food truck is delivered.

inputFormat

The input consists of two lines:

• The first line contains one integer n (1 ≤ n ≤ 10⁵) – the number of food trucks.
• The second line contains n tokens, each being one of the characters M, F or B, representing the type of each food truck in the order they arrive.

outputFormat

Output one line containing n numbers separated by spaces. The i-th number must be either 1 or 2, indicating that the i-th food truck is delivered to mine 1 or mine 2, respectively. If there are multiple optimal solutions, any one of them is acceptable.

sample

3
M F B

1 1 1