There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.

Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:   Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee n. If at the moment when it's time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).  When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.  When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.  The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction. 

You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of employees. 

The next line contains n characters. The i-th character is 'D' if the i-th employee is from depublicans fraction or 'R' if he is from remocrats.


-----Output-----

Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.


-----Examples-----
Input
5
DDRRR

Output
D

Input
6
DDRRRR

Output
R



-----Note-----

Consider one of the voting scenarios for the first sample:   Employee 1 denies employee 5 to vote.  Employee 2 denies employee 3 to vote.  Employee 3 has no right to vote and skips his turn (he was denied by employee 2).  Employee 4 denies employee 2 to vote.  Employee 5 has no right to vote and skips his turn (he was denied by employee 1).  Employee 1 denies employee 4.  Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = input()
countr = s.count('R')
countd = n - countr
cr = 0
cd = 0
i = 0
news = []
while countr != 0 and countd != 0:
    if s[i] == 'D':
        if cd == 0:
            cr += 1
            countr -= 1
            news.append('D')
        else:
            cd -= 1
    else:
        if cr == 0:
            cd += 1
            countd -= 1
            news.append('R')
        else:
            cr -= 1
    i += 1
    if i >= n:
        s = list(news)
        news = []
        n = len(s)
        i = 0
        
if countr > 0:
    print('R')
else:
    print('D')

n = int(input())
a = []
for i in input():
    a.append(i)
r, d = 0, 0
was_r, was_d = True, True
while True:
    if was_r and was_d:
        was_r, was_d = False, False
    else:
        break
    for i in range(len(a)):
        if a[i] == "R":
            was_r = True
            if r != 0:
                r -= 1
                a[i] = 0
            else:
                d += 1
        elif a[i] == "D":
            was_d = True
            if d != 0:
                d -= 1
                a[i] = 0
            else:
                r += 1
if was_r:
    print("R")
else:
    print("D")


def get_opposite_vote(vote):
    return 'R' if vote == 'D' else 'D'


def codeforces(votes):
    # rs = votes.count('R')
    # ds = votes.count('D')
    blocked = {'R': 0, 'D': 0}

    while True:
        new_votes = ''
        for vote in votes:
            if blocked[vote] > 0:
                blocked[vote] -= 1
            else:
                blocked[get_opposite_vote(vote)] += 1
                new_votes += vote
        votes = new_votes

        if votes.count('R') == 0 or votes.count('D') == 0:
            break

    return votes[0]


_ = input()
votes = input()
print(codeforces(votes))


# Author: Maharshi Gor
from collections import deque
def read(t:type=int):
    return t(input())


def read_arr(t=int):
    return [t(i) for i in str(input()).split()]

D = deque()
R = deque()

k = read()
S = input()

n = len(S)

for i in range(len(S)):
    if S[i] == 'R':
        R.append(i)
    else:
        D.append(i)

while R and D:
    r = R.popleft()
    d = D.popleft()
    if r < d:
        R.append(r+n)
    else:
        D.append(d+n)

if R:
    print('R')
else:
    print('D')


n = int(input())
s = input()

dd = 0
dr = 0
while len(s) > 1:
    t = ''
    cd = 0
    cr = 0
    for c in s:
        if c == 'D':
            if dd > 0:
                dd -= 1
            else:
                dr += 1
                t += c
                cd += 1
        else:
            if dr > 0:
                dr -= 1
            else:
                dd += 1
                t += c
                cr += 1
    s = t
    if cd == 0:
        s = 'R'
        break
    if cr == 0:
        s = 'D'
        break
    if dd >= cd:
        s = 'R'
        break
    if dr >= cr:
        s = 'D'
        break
    
print(s[0])

n=int(input())
raby=[x for x in input()]
numD=0
numR=0
flag=True
while flag: 
    cR=0
    cD=0
    for ind in range(len(raby)):
        if raby[ind]=='D':
            cD+=1
            if numR==0:
                numD+=1
            else:
                raby[ind]='N'
                numR-=1
        if raby[ind]=='R':
            cR+=1
            if numD==0:
                numR+=1
            else:
                raby[ind]='N'
                numD-=1
    if cD==0 or cR==0:
            flag=False
if numD==0:
    print('R')
else:
    print('D')

n = int(input())
s = list(input())
curr_d = 0
curr_r = 0
ost_d = s.count("D")
ost_r = s.count("R")
while True:
    for i in range(len(s)):
        if s[i] == "D":
            if curr_d > 0:
                s[i] = "N"
                ost_d -=1
                curr_d -= 1
            else:
                curr_r += 1
        if s[i] == "R":
            if curr_r > 0:
                s[i] = "N"
                ost_r -= 1
                curr_r -= 1
            else:
                curr_d += 1
    if ost_d == 0 or ost_r == 0:
        break
if ost_d == 0:
    print("R")
else:
    print("D")

input()
s = list(input())
r, d = map(s.count, ('R', 'D'))
rf, df = 0, 0

while r > 0 and d > 0:
    for i, v in enumerate(s):
        if v == 'D':
            if rf:
                rf -= 1
                d -= 1
                s[i] = ' '
            else:
                df += 1
        elif v == 'R':
            if df:
                df -= 1
                r -= 1
                s[i] = ' '
            else:
                rf += 1

print('D' if d else 'R')

n=int(input())
s=input()
dd,dr=0,0
dr = 0
while len(s) > 1:
    cd,cr,t=0,0,''
    for c in s:
        if c == 'D':
            if dd > 0:
                dd -= 1
            else:
                dr += 1
                t += c
                cd += 1
        else:
            if dr > 0:
                dr-=1
            else:
                dd+=1
                t+=c
                cr+=1
    s=t
    if cd == 0:
        s='R'
        break
    if cr==0:
        s='D'
        break
    if dd>=cd:
        s='R'
        break
    if dr>=cr:
        s='D'
        break
print(s[0])

input()
a = list(input()) + ['']
cnt = 0

while len(set(a)) == 3:
    for i, v in enumerate(a):
        if v == 'D':
            if cnt < 0:
                a[i] = ''
            cnt += 1
        if v == 'R':
            if cnt > 0:
                a[i] = ''
            cnt -= 1

for ss in set(a):
    if ss:
        print(ss)



from collections import deque

n = int(input())
s = input()
R, D = deque(), deque()

for num in range(n):
    if s[num] == 'D':
        D.append(num)
    else:
        R.append(num)

while D and R:
    d = D.popleft()
    r = R.popleft()
    if d < r:
        D.append(d+n)
    else:
        R.append(r+n)

if D:
    print('D')
else:
    print('R')


from collections import deque

n = int(input())
s = input()

d = deque()
r = deque()

for i, c in enumerate(s):
    if c == 'D':
        d.append(i)
    else:
        r.append(i)

while len(d) > 0 and len(r) > 0:
    if d[0] < r[0]:
        d.append(d.popleft() + n)
        r.popleft()
    else:
        d.popleft()
        r.append(r.popleft() + n)

print('D' if len(d) > 0 else 'R')
    


from collections import deque
n, s, D, R = int(input()), input(), deque(), deque()
for i in range(n):
    if s[i] == "D":
        D.append(i)
    else:
        R.append(i)
while len(D) and len(R):
    if D[0] < R[0]:
        D.append(D.popleft() + n)
        R.popleft()
    else:
        R.append(R.popleft() + n)
        D.popleft()
if len(D):
    print("D")
else:
    print("R")

from collections import deque

n = int(input())
a = [x for x in input()]

r1, r2 = int(0), int(0)

for x in a:
	if x == 'R':
		r1 += 1
	else:
		r2 += 1

q = deque(a)

c1, c2 = int(0), int(0)

while True:
	now = q.popleft()
	if not r1 or not r2:
		print(now)
		break
	if now == 'R':
		if c2:
			c2 -= 1
			r1 -= 1
		else:
			c1 += 1
			q.append(now)
	else:
		if c1:
			c1 -= 1
			r2 -= 1
		else:
			c2 += 1
			q.append(now)


from collections import deque  

n = int(input())
line = list(input())

D = deque()
R = deque()

for i in range(n):
    if line[i] == 'D':
        D.append(i)
    else:
        R.append(i)


while D and R:
    d = D.popleft()
    r = R.popleft()
    if d < r:
        D.append(d + n)
    else:
        R.append(r + n)

if D:
    print('D')
else:
    print('R')

s = input()
a = list(input())
a.append('')
cnt = 0

while len(set(a)) == 3:
    for i in range(len(a)):
    
        if a[i] == 'D':
            if cnt < 0:
                a[i] = ''
            cnt+=1
        if a[i] == 'R':
            if cnt > 0:
                a[i] = ''
            cnt-=1

for ss in set(a):
    if ss:
        print(ss)


from collections import deque
n = int(input())
s = input()
d = deque()
r = deque()
for i in range(n):
    if s[i] == 'D':
        d.append(i)
    else:
        r.append(i)
while True:
    # print('D',d)
    # print('R',r)
    
    if not d:
        print('R')
        break
    if not r:
        print('D')
        break    
    if d[0] < r[0]:
        r.popleft()
        d.append(d.popleft()+n)
    else:
        d.popleft()
        r.append(r.popleft()+n)

from collections import deque
D = deque()
R = deque()
n = int(input())
people = input()
for i in range(len(people)):
    if people[i] == "D":
        D.append(i)
    else:
        R.append(i)
while D and R:
    topr, topd = R.popleft(), D.popleft()
    if topr < topd:
        R.append(topr + n)
    else:
        D.append(topd + n)
if R:
    print("R")
else:
    print("D")


from collections import deque

q = deque()
n = int(input())
s = input()
for let in s:
    q.append(let)
    
b = 0
while len(q) > 1 and abs(b) < 400000:
    #print(b)
    c = q.popleft()
    if c == 'D':
        if b >= 0:
            q.append(c)
        b += 1
    if c == 'R':
        if b <= 0:
            q.append(c)
        b -= 1

print(q.pop())

s = input()
a = list(input())
a.append('')
cnt = 0

while len(set(a)) == 3:
    for i in range(len(a)):
    
        if a[i] == 'D':
            if cnt < 0:
                a[i] = ''
            cnt+=1
        if a[i] == 'R':
            if cnt > 0:
                a[i] = ''
            cnt-=1

for ss in set(a):
    if ss:
        print(ss)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
class lq(list):
	def __init__(self):
		self.value=[]
		self.lenght=0
		self.startPos=0
		self.maxLen = 50000
	def append(self, item):
		self.value.append(item)
		self.lenght+=1
	def pop(self):
		if self.startPos < self.maxLen:
			rv= self.value[self.startPos]
			self.lenght-=1
			self.startPos+=1
			return rv
		else:
			rv= self.value[self.startPos]
			self.lenght-=1
			self.value[0:(self.startPos+1)]=[]
			self.startPos=0
			return rv

n = int(input())
s = input()

qforD = lq()
qforR = lq()
for i in range(n):
	if s[i] == 'D':
		qforD.append(i)
	else:
		qforR.append(i)
cnt = n
while qforD.lenght>0 and qforR.lenght>0:
	dNum=qforD.pop()
	rNum=qforR.pop()
	if dNum < rNum:
		qforD.append(cnt)
	else:
		qforR.append(cnt)
	cnt+=1
if qforD.lenght == 0:
	print('R')
else:
	print('D')

	


#
# Created by Daniil Kozhanov. All rights reserved.
#               december 2016

n = int(input())
s = input()
u = [1] * n
u1 = 0
u2 = 0
c1 = s.count("D")
c2 = s.count("R")

while c1 != 0 and c2 !=0:
    for i in range(n):
        if s[i] == "D":
            if u[i] == 1:
                if u1 > 0:
                    u1 -= 1
                    u[i] -= 1
                    c1 -= 1
                else:
                    u2 += 1
        else:
            if u[i] == 1:
                if u2 > 0:
                    u2 -= 1
                    u[i] -= 1
                    c2 -= 1
                else:
                    u1 += 1

if c2 == 0:
    print("D")
else:
    print("R")


import collections
n = int(input())
s = input()
R, D = collections.deque(), collections.deque()

for i in range(n):
    if s[i] == 'R': R.append(i)
    else: D.append(i)


#print(R)
#print(D)
    
while R and D:
    r = R.popleft()
    d = D.popleft()
    #print(str(r) + " is R and D " + str(d))
    if r < d:
        R.append(n + r)
    else:
        D.append(n + d)

if D:
    print('D')
else:
    print('R')

a = int(input())
s = input()
b = []
for c in s:
    if c == 'D':
        b.append(1)
    else:
        b.append(0)
cnt = [0] * 2
while True:
    c = []
    for x in b:
        if cnt[x] > 0:
            cnt[x] -= 1;
        else:
            c.append(x);
            cnt[1 - x] += 1;
    if c == b:
        break
    b = c
if b[0] == 0:
    print('R')
else:
    print('D')


n = input()
a = input()
cnt = 0
while len(set(a)) == 2:
    new_a = []
    for i in range(len(a)):
        if a[i] == 'D':
            if cnt >= 0:
                new_a.append(a[i])
            cnt += 1
        else:
            if cnt <= 0:
                new_a.append(a[i])
            cnt -= 1
    a = new_a
print(a[0])