Hat Guessing Strategy

There are N OIers each wearing either a red or a white hat. Each contestant can see all the hats of the others, but not his own. They want to agree on a guessing strategy such that for any configuration of hats (of which there are \(2^N\) possibilities), the following conditions hold:

• If there are \(b\) white hats, then at least \(\lfloor b/2 \rfloor\) of the white‐hatted contestants guess their own hat color correctly.
• If there are \(c\) red hats, then at least \(\lfloor c/2 \rfloor\) of the red‐hatted contestants guess their own hat color correctly.

A strategy that works is as follows. Before the contest, the contestants are arbitrarily paired (if \(N\) is odd, one contestant remains unpaired). In each pair, denote the contestant with the lower index as the lower member and the one with the higher index as the upper member. The strategy is:

1. The lower member in every pair always guesses white regardless of what he sees.
2. The upper member in the pair, who can see the lower member’s hat color, guesses exactly that color.
3. If there is an unpaired contestant (when \(N\) is odd), he simply guesses white.

Let us check this strategy:

• Pair with same colors:
  • If both wear white, lower guesses white (correct) and upper sees white and guesses white (correct).
  • If both wear red, lower guesses white (incorrect) but upper sees red and guesses red (correct).
• Pair with different colors:
  • If the pair is (white, red) then lower (white) guesses white (correct) while upper sees white and guesses white (incorrect since his hat is red).
  • If the pair is (red, white) then lower (red) guesses white (incorrect) but upper sees red and guesses red (correct since his hat is white? Note that in this case the upper member is white, but his guess is red, so he is incorrect). However, an adversary cannot force all contestants of a given color to be in the position that makes them guess incorrectly. In every pair, exactly one contestant is guaranteed a correct guess for his hat’s color. A short parity argument shows that in the worst case at least \(\lfloor b/2\rfloor\) white-hatted and \(\lfloor c/2\rfloor\) red-hatted contestants are correct.

  This strategy is valid because when the contestants are paired in advance, an adversary assigning hat colors cannot force less than \(\lfloor b/2\rfloor\) of the white hats (and similarly for red hats) to be in the position that guesses correctly.

  ---

  Note: Although the lower member does not have information about his own hat, committing to guess white in every pair forces the adversary—in the worst‐case allocation—to allow at least half of the contestants in each color to guess correctly.

  inputFormat

  The input consists of two lines. The first line contains a single integer \(N\) (\(1 \le N \le 10^5\)), the number of contestants. The second line contains a string of length \(N\) comprised only of characters 'W' and 'R', representing the actual hat colors of the contestants in order (where 'W' stands for white and 'R' stands for red).

  outputFormat

  Output a string of length \(N\) where the \(i\)th character is the guessed hat color ('W' or 'R') for the \(i\)th contestant according to the strategy.

  sample

  4
  WRRW

  W W R W
  

  </p>