/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 600 点
問題文
N 個のブロックが横一列に並んでおり、それぞれのブロックは青・白・赤のうちいずれかで塗られています。
左から i 番目 (1 \leq i \leq N) のブロックの色は文字 c_i で表され、B は青、W は白、R は赤に対応しています。
この状態から青・白・赤のブロックを積み上げ、N 段のピラミッドの形にします。以下の図がその一例です。
ここでは、ブロックを下から順に、以下の規則で 1 個ずつ置いていきます。
- 直下にある 2 個のブロックの色が同じ場合、それと同じ色のブロックを置く
- 直下にある 2 個のブロックの色が異なる場合、そのどちらでもない色のブロックを置く
このとき、一番上のブロックはどの色になるでしょうか？
制約
- N は 2 \leq N \leq 400000 を満たす整数
- c_1, c_2, \dots, c_N はそれぞれ
B，W，Rのいずれか
入力
入力は以下の形式で標準入力から与えられます。
N c_1c_2\cdotsc_N
出力
一番上のブロックの色が青ならば B、白ならば W、赤ならば R を出力してください。
入力例 1
3 BWR
出力例 1
W
この入力例では、ブロックを以下のように積み上げることになります。
- 一番下の段の左から 1, 2 番目のブロックはそれぞれ青色・白色なので、その上に赤色のブロックを置く。
- 一番下の段の左から 2, 3 番目のブロックはそれぞれ白色・赤色なので、その上に青色のブロックを置く。
- 下から 2 段目のブロックはそれぞれ赤色・青色なので，その上に白色のブロックを置く。
一番上のブロックの色は白となるため、W を出力します。
入力例 2
4 RRBB
出力例 2
W
この入力例では、ブロックを以下のように積み上げることになります。
- 一番下の段の左から 1, 2 番目のブロックはそれぞれ赤色・赤色なので、その上に赤色のブロックを置く。
- 一番下の段の左から 2, 3 番目のブロックはそれぞれ赤色・青色なので、その上に白色のブロックを置く。
- 一番下の段の左から 3, 4 番目のブロックはそれぞれ青色・青色なので、その上に青色のブロックを置く。
- 下から 2 段目の左から 1, 2 番目のブロックはそれぞれ赤色・白色なので、その上に青色のブロックを置く。
- 下から 2 段目の左から 2, 3 番目のブロックはそれぞれ白色・青色なので、その上に赤色のブロックを置く。
- 下から 3 段目のブロックはそれぞれ青色・赤色なので、その上に白色のブロックを置く。
一番上のブロックの色は白となるため、W を出力します。
入力例 3
6 BWWRBW
出力例 3
B
最終的なブロックの並びは、以下の図のように表されます。一番上のブロックの色は青となるため、B を出力します。
なお、これは問題文中に例示したケースと同じものになっています。
入力例 4
8 WWBRBBWB
出力例 4
R
最終的なブロックの並びは、以下の図のように表されます。一番上のブロックの色は赤となるため、R を出力します。
入力例 5
21 BWBRRBBRWBRBBBRRBWWWR
出力例 5
B
Score : 600 points
Problem Statement
We have N blocks arranged in a row, where each block is painted blue, white, or red.
The color of the i-th block from the left (1 \leq i \leq N) is represented by a character c_i; B, W, and R stand for blue, white, and red, respectively.
From this situation, we will pile up blue, white, and red blocks to make a pyramid with N steps. The following figure shows an example of this:
Here, we place blocks one by one from bottom to top as follows:
- if the two blocks immediately below a position have the same color, we will place there a block of the same color;
- if the two blocks immediately below a position have different colors, we will place there a block of the color different from those two colors.
What will be the color of the block at the top?
Constraints
- N is an integer satisfying 2 \leq N \leq 400000.
- Each of c_1, c_2, \dots, c_N is
B,W, orR.
Input
Input is given from Standard Input in the following format:
N c_1c_2\cdotsc_N
Output
If the topmost block will be blue, print B; if it will be white, print W; if it will be red, print R.
Sample Input 1
3 BWR
Sample Output 1
W
In this case, we will pile up blocks as follows:
- the 1-st and 2-nd blocks from the left in the bottom row are respectively blue and white, so we place a red block on top of it;
- the 2-nd and 3-rd blocks from the left in the bottom row are respectively white and red, so we place a blue block on top of it;
- the blocks in the 2-nd row from the bottom are respectively red and blue, so we place a white block on top of it.
Thus, the block at the top will be white; we should print W.
Sample Input 2
4 RRBB
Sample Output 2
W
In this case, we will pile up blocks as follows:
- the 1-st and 2-nd blocks from the left in the bottom row are both red, so we place a red block on top of it;
- the 2-nd and 3-rd blocks from the left in the bottom row are respectively red and blue, so we place a white block on top of it;
- the 3-rd and 4-th blocks from the left in the bottom row are both blue, so we place a blue block on top of it;
- the 1-st and 2-nd blocks from the left in the 2-nd row from the bottom are respectively red and white, so we place a blue block on top of it;
- the 2-nd and 3-rd blocks from the left in the 2-nd row from the bottom are respectively white and blue, so we place a red block on top of it;
- the blocks in the 3-rd row from the bottom are respectively blue and red, so we place a white block on top of it.
Thus, the block at the top will be white; we should print W.
Sample Input 3
6 BWWRBW
Sample Output 3
B
The figure below shows the final arrangement of blocks. The block at the top will be blue; we should print B.
Note that this is the case shown as an example in Problem Statement.
Sample Input 4
8 WWBRBBWB
Sample Output 4
R
The figure below shows the final arrangement of blocks. The block at the top will be red; we should print R.
Sample Input 5
21 BWBRRBBRWBRBBBRRBWWWR
Sample Output 5
B