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: MEDIUM
Tags: Amortized analysis

Implementation

Greedy algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
n = int(input())
arr = list(input())
r = arr.count('R')
d = arr.count('D')
i = j = 0
while r > 0 and d > 0:
	while arr[j] == arr[i] or arr[j] == 'O':
		j = (j + 1) % n
	if arr[j] == 'R':
		r -= 1
	else:
		d -= 1
	arr[j] = 'O'
	c = i
	i = (i + 1) % n
	while arr[i] == 'O':
		i = (i + 1) % n
	if i < c:
		j = i = 0
		n = r + d
		for x in range(n):
			while arr[i] == 'O':
				i += 1
			arr[j] = arr[i]
			j += 1
			i += 1
		i = j = 0
if r > 0:
	print('R')
else:
	print('D')


class Node:

	def __init__(self, val=None, prev=None, next=None):
		self.val = val
		self.prev = prev
		self.next = next

class List:

	def __init__(self, first=None):
		self.first = first
		self.last = first

	def __add__(self, item):
		self.last.next = item
		item.prev = self.last
		self.last = item

	def __delete__(self, item):
		if self.first == item:
			self.first = self.first.next
			self.first.prev = None
		elif self.last == item:
			self.last = self.last.prev
			self.last.next = None
		else:
			item.prev.next = item.next
			item.next.prev = item.prev
n = int(input())
str = input()
ds = 0
rs = 0
list = List(Node(str[0]))
if str[0] == 'D':
	ds += 1
else:
	rs += 1
for i in range(1, n):
	list.__add__(Node(str[i]))
	if str[i] == 'D':
		ds += 1
	else:
		rs += 1
removeR = 0
removeD = 0
while ds > 0 and rs > 0:
	node = list.first
	while node != None and ds > 0 and (rs > 0):
		if node.val == 'D' and removeD > 0:
			list.__delete__(node)
			removeD -= 1
			ds -= 1
		elif node.val == 'R' and removeR > 0:
			list.__delete__(node)
			removeR -= 1
			rs -= 1
		elif node.val == 'R':
			removeD += 1
		elif node.val == 'D':
			removeR += 1
		node = node.next
if rs > 0:
	print('R')
if ds > 0:
	print('D')


from collections import deque
s = deque()
n = int(input())
s1 = deque()
l = str(input())
for x in range(n):
	if l[x] == 'D':
		s.append(x)
	else:
		s1.append(x)
for x in range(n):
	if len(s) != 0 and len(s1) != 0:
		if s[0] < s1[0]:
			s1.popleft()
			s.popleft()
			s.append(x + n)
		else:
			s.popleft()
			s1.popleft()
			s1.append(x + n)
if len(s) == 0:
	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
		elif 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])


from collections import deque
n = int(input())
p = list(input())
rq = deque()
dq = deque()
for (i, e) in enumerate(p):
	if e == 'D':
		dq.append(i)
	else:
		rq.append(i)
while rq and dq:
	d = dq.popleft()
	r = rq.popleft()
	if d > r:
		rq.append(r + n)
	else:
		dq.append(d + n)
if rq:
	print('R')
else:
	print('D')


n = int(input())
s = list(input()) + ['#']
d = r = 0
di = {}
di['D'] = 0
di['R'] = 0
for i in range(n):
	di[s[i]] += 1
while di['D'] != 0 and di['R'] != 0:
	for i in range(n):
		if s[i] == '@':
			continue
		if s[i] == 'D':
			if r < d:
				r = d
			while s[r % n] != 'R':
				r += 1
			s[r % n] = '@'
			di['R'] -= 1
		elif s[i] == 'R':
			if d < r:
				d = r
			while s[d % n] != 'D':
				d += 1
			s[d % n] = '@'
			di['D'] -= 1
		if di['D'] == 0:
			print('R')
			exit()
		elif di['R'] == 0:
			print('D')
			exit()
if di['D'] == 0:
	print('R')
elif di['R'] == 0:
	print('D')


n = int(input())
s = list(input())
(r, d) = (0, 0)
while True:
	t = 0
	for i in range(n):
		if s[i] == 'D':
			if d > 0:
				s[i] = '0'
				d -= 1
				t += 1
			else:
				r += 1
		if s[i] == 'R':
			if r > 0:
				s[i] = '0'
				r -= 1
				t += 1
			else:
				d += 1
	if t == 0:
		for i in range(n):
			if s[i] != '0':
				print(s[i])
				exit()


s = input()
a = list(input())
a.append('')
count = 0
while len(set(a)) == 3:
	for i in range(len(a)):
		if a[i] == 'D':
			if count < 0:
				a[i] = ''
			count += 1
		if a[i] == 'R':
			if count > 0:
				a[i] = ''
			count -= 1
for ss in set(a):
	if ss:
		print(ss)


amount = int(input())
people = list(input())
D = people.count('D')
R = people.count('R')
ignore = set()
igR = 0
igD = 0
while True:
	for k in range(amount):
		if k not in ignore:
			if people[k] == 'R' and igR > 0:
				igR -= 1
				ignore.add(k)
			elif people[k] == 'D' and igD > 0:
				igD -= 1
				ignore.add(k)
			elif people[k] == 'R':
				igD += 1
				D -= 1
			else:
				igR += 1
				R -= 1
	if R <= 0:
		print('D')
		break
	elif D <= 0:
		print('R')
		break


from collections import deque
n = int(input())
s = input()
(r, d) = (deque(), deque())
for (a, i) in enumerate(s):
	if i == 'R':
		r.appendleft(a)
	else:
		d.appendleft(a)
while len(r) and len(d):
	R = r.pop()
	D = d.pop()
	if R < D:
		r.appendleft(R + n)
	else:
		d.appendleft(D + n)
print(['R', 'D'][len(d) > 0])


n = input()
s = input()
(cD, cR, aD, aR) = (0, 0, 0, 0)
for i in s:
	if i == 'D':
		aD += 1
	else:
		aR += 1
while aD > 0 and aR > 0:
	x = ''
	for i in s:
		if i == 'D':
			if cD > 0:
				cD -= 1
				aD -= 1
			else:
				cR += 1
				x += i
		if i == 'R':
			if cR > 0:
				cR -= 1
				aR -= 1
			else:
				cD += 1
				x += i
	s = x
if aD == 0:
	print('R')
else:
	print('D')


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')


from array import array
n = int(input())
s = list(input())
cR = 0
cD = 0
new_s = s
while len(set(new_s)) == 2:
	s = new_s
	new_s = list()
	for c in s:
		if c == 'R':
			if cR == 0:
				new_s.append('R')
				cD += 1
			else:
				cR -= 1
		elif c == 'D':
			if cD == 0:
				new_s.append('D')
				cR += 1
			else:
				cD -= 1
print(new_s[0])


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
n = int(input())
s = [*input()]
R = deque()
D = deque()
for i in range(n):
	if s[i] == 'R':
		R.append(i)
	else:
		D.append(i)
l = n - 1
while True:
	l += 1
	if not R:
		print('D')
		break
	if not D:
		print('R')
		break
	if R[0] < D[0]:
		D.popleft()
		v = R.popleft()
		R.append(l)
	else:
		R.popleft()
		v = D.popleft()
		D.append(l)


n = int(input())
s = input()
ds = []
rs = []
for i in range(n):
	if s[i] == 'R':
		rs += [i]
	else:
		ds += [i]
while len(ds) != 0 and len(rs) != 0:
	ds2 = []
	rs2 = []
	num = 0
	num2 = 0
	while num < len(ds) and num2 < len(rs):
		if ds[num] > rs[num2]:
			rs2 += [rs[num2]]
		else:
			ds2 += [ds[num]]
		num += 1
		num2 += 1
	i = num
	while i < len(ds):
		ds2 += [ds[i]]
		i += 1
	i = num2
	while i < len(rs):
		rs2 += [rs[i]]
		i += 1
	if len(rs) - num2 == len(ds):
		ds = []
		break
	if len(ds) - num == len(rs):
		rs = []
		break
	ds = ds2[len(rs) - num2:]
	rs = rs2[len(ds) - num:]
if len(ds) == 0:
	print('R')
else:
	print('D')


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')


read = lambda : map(int, input().split())
n = int(input())
s = input() * 3
n2 = n * 20
was = [0] * n
ri = di = 1
while ri < n2 and s[ri % n] != 'R':
	ri += 1
while di < n2 and s[di % n] != 'D':
	di += 1
cnt = n
i = 0
nx = [0] * n
while cnt > 1:
	if di == i:
		di += 1
		while di < n2 and (s[di % n] != 'D' or was[di % n]):
			di += 1
	if ri == i:
		ri += 1
		while ri < n2 and (s[ri % n] != 'R' or was[ri % n]):
			ri += 1
	if s[i % n] == 'R':
		if di < n2:
			was[di % n] = 1
			di += 1
			while di < n2 and (s[di % n] != 'D' or was[di % n]):
				di += 1
		elif ri < n2:
			was[ri % n] = 1
			ri += 1
			while ri < n2 and (s[ri % n] != 'R' or was[ri % n]):
				ri += 1
		else:
			cnt += 1
	elif ri < n2:
		was[ri % n] = 1
		ri += 1
		while ri < n2 and (s[ri % n] != 'R' or was[ri % n]):
			ri += 1
	elif di < n2:
		was[di % n] = 1
		di += 1
		while di < n2 and (s[di % n] != 'D' or was[di % n]):
			di += 1
	else:
		cnt += 1
	cnt -= 1
	j = i
	i += 1
	while was[i % n]:
		i += 1
	nx[j % n] = i
ind = was.index(0)
ans = s[ind]
print(ans)


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 queue import PriorityQueue
from queue import Queue
import math
from collections import *
import sys
import operator as op
from functools import reduce
MOD = int(1000000000.0 + 7)
input = sys.stdin.readline
ii = lambda : list(map(int, input().strip().split()))
ist = lambda : list(input().strip())
MOD = int(1000000000.0 + 7)
input = sys.stdin.readline
ii = lambda : list(map(int, input().strip().split()))
ist = lambda : list(input().strip())
(n,) = ii()
s = input()
(r, d) = (deque(), deque())
for k in range(n):
	if s[k] == 'R':
		r.appendleft(k)
	else:
		d.appendleft(k)
while len(r) and len(d):
	w1 = r.pop()
	w2 = d.pop()
	if w1 < w2:
		r.appendleft(w1 + n)
	else:
		d.appendleft(w2 + n)
print(['R', 'D'][len(d) > 0])


from collections import deque
n = int(input())
strr = input()
d = deque()
r = deque()
cnt = 0
for elem in strr:
	if elem == 'D':
		d.append(cnt)
		cnt += 1
	else:
		r.append(cnt)
		cnt += 1
while len(d) and len(r):
	dFirst = d.popleft()
	rFirst = r.popleft()
	if dFirst < rFirst:
		d.append(cnt)
		cnt += 1
	else:
		r.append(cnt)
		cnt += 1
if len(d):
	print('D')
else:
	print('R')


n = int(input())
v = list(input())
from collections import deque
d = deque()
cur = 'X'
cnt = 0
for i in range(n):
	if v[i] == cur:
		cnt += 1
	else:
		if cnt > 0:
			d.append((cur, cnt))
		cur = v[i]
		cnt = 1
if cnt > 0:
	d.append((v[-1], cnt))
while len(d) > 1:
	v = d.popleft()
	v2 = d.popleft()
	if v[0] == v2[0]:
		d.appendleft((v[0], v[1] + v2[1]))
	elif v[1] >= v2[1]:
		if v[1] > v2[1]:
			d.appendleft((v[0], v[1] - v2[1]))
		d.append((v[0], v2[1]))
	else:
		d.appendleft((v2[0], v2[1] - v[1]))
		d.append((v[0], v[1]))
print(d.pop()[0])


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 = int(input())
s = input()
t = []
d = r = 0
for i in s:
	t.append(i)
while len(t) != 1:
	for i in range(len(t)):
		if t[i] == 'R' and d == 0:
			r += 1
		elif t[i] == 'D' and r == 0:
			d += 1
		elif t[i] == 'R' and d != 0:
			d -= 1
			t[i] = 0
		else:
			r -= 1
			t[i] = 0
	k = []
	for i in t:
		if i != 0:
			k.append(i)
	t = k[:]
	k.sort()
	if len(k) != 1:
		if k[0] == k[len(k) - 1]:
			break
print(t[0])


n = int(input())
s = input()
cd = 0
cr = 0
cntd = 0
cntr = 0
for i in range(n):
	if s[i] == 'D':
		cntd += 1
	else:
		cntr += 1
a = [1] * n
while cntd and cntr:
	for i in range(n):
		if a[i]:
			if s[i] == 'D':
				if cd == 0:
					cr += 1
				else:
					cd -= 1
					a[i] = 0
					cntd -= 1
			elif cr == 0:
				cd += 1
			else:
				cr -= 1
				a[i] = 0
				cntr -= 1
if not cntd:
	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')


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


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')


n = int(input())
v = input()
v = [v[i] for i in range(n)]
d = r = 0
while len(set(v) - set([0])) != 1:
	for j in range(n):
		i = v[j]
		if i == 'D' and d < 0:
			(d, v[j]) = (d + 1, 0)
		elif i == 'R' and r < 0:
			(r, v[j]) = (r + 1, 0)
		elif i == 'D':
			r -= 1
		elif i == 'R':
			d -= 1
print(list(set(v) - set([0]))[0])


from collections import defaultdict
n = int(input())
s = input()

class List:

	class Node:

		def __init__(self, val):
			self.val = val
			self.prev = None
			self.next = None

		def __str__(self):
			return self.val

	def __init__(self):
		self.head = None

	def append(self, val):
		if self.head is not None:
			tail = self.head.prev
			tail.next = List.Node(val)
			tail.next.prev = tail
			tail.next.next = self.head
			self.head.prev = tail.next
		else:
			self.head = List.Node(val)
			self.head.prev = self.head
			self.head.next = self.head

	def remove(self, x):
		if x is self.head:
			self.head = x.next
		x.prev.next = x.next
		x.next.prev = x.prev

	def __str__(self):
		if self.head is None:
			return ''
		res = '%s' % self.head.val
		x = self.head.next
		while x is not self.head:
			res += x.val
			x = x.next
		return res

def main():
	if n == 1:
		print(s[0])
		return
	lst = List()
	count = defaultdict(int)
	for c in s:
		lst.append(c)
		count[c] += 1
	cur = lst.head
	dem = 0
	rep = 0
	while count['R'] > 0 and count['D'] > 0:
		if cur.val == 'D':
			if rep == 0:
				dem += 1
			else:
				rep -= 1
				lst.remove(cur)
				count[cur.val] -= 1
		elif dem == 0:
			rep += 1
		else:
			dem -= 1
			lst.remove(cur)
			count[cur.val] -= 1
		if cur is cur.next:
			break
		cur = cur.next
	if count['D'] > count['R']:
		print('D')
	else:
		print('R')
main()


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')


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

def codeforces(votes):
	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))


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


n = input()
a = input()
num = 0
while num < len(a):
	b = '-'
	num = 0
	aa = ''
	for i in a:
		if b != i:
			if num > 0:
				num -= 1
			else:
				num = 1
				b = i
				aa += i
		else:
			num += 1
			aa += i
	a = ''
	for i in aa:
		if i != b and num > 0:
			num -= 1
		else:
			a += i
print(a[0])


import heapq
n = int(input())
s = input()
(r, d) = ([], [])
for (a, i) in enumerate(s):
	if i == 'R':
		heapq.heappush(r, a)
	else:
		heapq.heappush(d, a)
while len(r) and len(d):
	R = heapq.heappop(r)
	D = heapq.heappop(d)
	if R < D:
		heapq.heappush(r, R + n)
	else:
		heapq.heappush(d, D + n)
print(['R', 'D'][len(d) > 0])


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:
	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
n = int(input())
s = input()
s = list(s)
D = deque([])
R = deque([])
cnt = 1
for i in range(n):
	if s[i] == 'D':
		D.append(i)
	else:
		R.append(i)
while True:
	if len(D) == 0 or len(R) == 0:
		break
	a = D.popleft()
	b = R.popleft()
	if a < b:
		D.append(a + n)
	else:
		R.append(b + n)
if len(D):
	print('D')
else:
	print('R')


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')


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])


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
		elif 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 sys
input = sys.stdin.readline
n = int(input())
vote = input()
ignore = set()
d = 0
r = 0
while True:
	new = False
	for i in range(n):
		if i not in ignore:
			if vote[i] == 'D':
				if r == 0:
					d += 1
				else:
					r -= 1
					ignore.add(i)
					new = True
			elif d == 0:
				r += 1
			else:
				d -= 1
				ignore.add(i)
				new = True
	if not new:
		break
ans = set(range(n)) - ignore
print(vote[ans.pop()])


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')


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:
	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())


n = int(input())
vote_order = input()
vote_order = [i for i in vote_order]
d = 0
r = 0
set_with_del = set([0])
while len(set(vote_order) - set_with_del) != 1:
	for i in range(n):
		if vote_order[i] == 'D':
			if d < 0:
				d += 1
				vote_order[i] = 0
			else:
				r -= 1
		elif vote_order[i] == 'R':
			if r < 0:
				r += 1
				vote_order[i] = 0
			else:
				d -= 1
print(list(set(vote_order) - set_with_del)[0])


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')


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 = deque()
D = deque()
for i in range(n):
	if s[i] == 'D':
		D.append(i)
	else:
		R.append(i)
k = 0
while len(R) and len(D):
	a = R.popleft()
	b = D.popleft()
	if a == k:
		R.append(a + n)
	elif b == k:
		D.append(b + n)
	else:
		R.appendleft(a)
		D.appendleft(b)
	k += 1
if len(R):
	print('R')
else:
	print('D')


from collections import deque
n = int(input())
voters = deque(input())
(ban_D, ban_R) = (0, 0)
(out_D, out_R) = (0, 0)
(num_D, num_R) = (voters.count('D'), voters.count('R'))
while True:
	x = voters[0]
	voters.rotate(-1)
	if x == 'D':
		if ban_D:
			ban_D -= 1
			voters.pop()
			out_D += 1
		else:
			if out_R == num_R:
				print('D')
				break
			ban_R += 1
	elif x == 'R':
		if ban_R:
			ban_R -= 1
			voters.pop()
			out_R += 1
		else:
			if out_D == num_D:
				print('R')
				break
			ban_D += 1


from collections import deque
a = int(input())
x = list(input())
D = deque([])
R = deque([])
for i in range(a):
	if x[i] == 'D':
		D.append(i)
	else:
		R.append(i)
while R and D:
	if D[0] > R[0]:
		D.popleft()
		R.rotate(-1)
		R[-1] += a
	else:
		R.popleft()
		D.rotate(-1)
		D[-1] += a
if D:
	print('D')
if R:
	print('R')


l = int(input())
a = input()
b = set()
(p, q) = (a.count('D'), a.count('R'))
(r, t) = (0, 0)
while p > 0 and q > 0:
	j = 0
	while j < l:
		if j in b:
			j += 1
			continue
		else:
			if a[j] == 'D':
				if r > 0:
					b.add(j)
					r = r - 1
					p = p - 1
				else:
					t = t + 1
			if a[j] == 'R':
				if t > 0:
					b.add(j)
					t = t - 1
					q = q - 1
				else:
					r = r + 1
			j += 1
		if p == 0 or q == 0:
			break
if p == 0:
	print('R')
else:
	print('D')


n = int(input())
s = input()
cd = s.count('D')
cr = s.count('R')
(pr, pd) = (0, 0)
x = [1] * n
f = ''
i = 0
while f == '':
	if s[i] == 'D':
		if x[i] != 0:
			if pd == 0:
				cr = cr - 1
				pr = pr + 1
				if cr <= 0:
					f = 'D'
					break
			else:
				pd = pd - 1
				x[i] = 0
	elif x[i] != 0:
		if pr == 0:
			cd = cd - 1
			pd = pd + 1
			if cd <= 0:
				f = 'R'
				break
		else:
			pr = pr - 1
			x[i] = 0
	i = (i + 1) % n
print(f)


from sys import *
n = int(stdin.readline())
dem = []
rep = []
dp = 0
rp = 0
s = stdin.readline()
for i in range(len(s)):
	if s[i] == 'D':
		dem.append(i)
	if s[i] == 'R':
		rep.append(i)
j = len(rep) + len(dem)
while dp < len(dem) and rp < len(rep):
	r = rep[rp]
	d = dem[dp]
	if r < d:
		rep.append(j)
	else:
		dem.append(j)
	j += 1
	rp += 1
	dp += 1
if len(dem) == dp:
	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')


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)
	elif c1:
		c1 -= 1
		r2 -= 1
	else:
		c2 += 1
		q.append(now)


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')


n = int(input())
a = list(input())
d = 0
r = 0
count_d = -1
count_r = -1
while count_d != 0 and count_r != 0:
	n = len(a)
	count_d = 0
	count_r = 0
	new_list = []
	while d < n and r < n:
		if a[d] != 'D':
			d += 1
		if a[r] != 'R':
			r += 1
		if d < n and r < n and (a[d] == 'D') and (a[r] == 'R'):
			if d < r:
				if d >= 0:
					new_list.append('D')
				count_d += 1
				if d < 0:
					a[r] = 'E'
			elif r < d:
				if r >= 0:
					new_list.append('R')
				count_r += 1
				if r < 0:
					a[d] = 'E'
			d += 1
			r += 1
	if r > n - 1:
		r = 0
		p = len(new_list)
		while d < n:
			if a[d] == 'D':
				new_list.append('D')
			d += 1
			count_d += 1
		d = -1 * (len(new_list) - p)
	if d > n - 1:
		d = 0
		p = len(new_list)
		while r < n:
			if a[r] == 'R':
				new_list.append('R')
			r += 1
			count_r += 1
		r = -1 * (len(new_list) - p)
	a = new_list.copy()
if count_d == 0:
	print('R')
elif count_r == 0:
	print('D')


import collections
n = int(input())
s = input()
(d, r) = (collections.deque([]), collections.deque([]))
for i in range(n):
	if s[i] == 'D':
		d.append(i + 1)
	else:
		r.append(i + 1)
ld = len(d)
lr = len(r)
while ld != 0 and lr != 0:
	if d[0] < r[0]:
		lr -= 1
		d.append(d[0] + n)
		d.popleft()
		r.popleft()
	else:
		ld -= 1
		r.append(r[0] + n)
		r.popleft()
		d.popleft()
if ld == 0:
	print('R')
else:
	print('D')


n = int(input())
s = input()
(D, R) = (s.count('D'), s.count('R'))
(d, r) = (0, 0)
p = [1] * n
ans = 0
i = 0
while ans == 0:
	if p[i]:
		if s[i] == 'D':
			if d > 0:
				d = d - 1
				p[i] = 0
			elif R > 0:
				R -= 1
				r = r + 1
			else:
				ans = 'D'
				break
		elif r > 0:
			r = r - 1
			p[i] = 0
		elif D > 0:
			D -= 1
			d = d + 1
		else:
			ans = 'R'
			break
	i = (i + 1) % n
print(ans)


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
	elif 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')