NOMURA Programming Competition 2020 - Postdocs

For a string S consisting of the uppercase English letters `P` and `D`, let the doctoral and postdoctoral quotient of S be the total number of occurrences of `D` and `PD` in S as contiguous substrings. For example, if S = `PPDDP`, it contains two occurrences of `D` and one occurrence of `PD` as contiguous substrings, so the doctoral and postdoctoral quotient of S is 3.

We have a string T consisting of `P`, `D`, and `?`.

Among the strings that can be obtained by replacing each `?` in T with `P` or `D`, find one with the maximum possible doctoral and postdoctoral quotient.

Constraints

* 1 \leq |T| \leq 2 \times 10^5
* T consists of `P`, `D`, and `?`.

Input

Input is given from Standard Input in the following format:


T


Output

Print one string with the maximum possible doctoral and postdoctoral quotient among the strings that can be obtained by replacing each `?` in T with `P` or `D`. If there are multiple such strings, you may print any of them.

Examples

Input

PD?D??P


Output

PDPDPDP


Input

P?P?


Output

PDPD

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t = input()
print(t.replace('?', 'D'))


T = input().replace('?', 'D')
print(T)


S = input()
SS = S.replace('?', 'D')
print(SS)


a = input()
print(a.replace('?', 'D'))


t = input()
qn = t.count('?')
print(t.replace('?', 'D'))


T = input()
T1 = T.replace('?', 'D')
print(T1)


T = input()
t = T.replace('?', 'D')
print(t)


S = str(input())
print(S.replace('?', 'D'))


t = input()
t_1 = t.replace('?', 'D')
print(t_1)


t = str(input())
ans = t.replace('?', 'D')
print(ans)


s = str(input())
nw1 = s.replace('?', 'D')
print(nw1)


T = input()
T_rep = T.replace('?', 'D')
print(T_rep)


str = input()
print(str.replace('?', 'D'))


n = input()
n = n.replace('?', 'D')
print(n)


l = input()
print(l.replace('?', 'D'))


t = input()
ret = t.replace('?', 'D')
print(ret)


print(''.join([x if x != '?' else 'D' for x in input()]))


import re
T = input()
t = re.sub('\\?', 'D', T)
print(t)


T = input()
now = 0
ans = ''
K = T.replace('?', 'D')
print(K)


T = str(input())
print(T.replace('?', 'D'))


T = input()
new_T = T.replace('?', 'D')
print(new_T)


S = input()
S = S.replace('?', 'D')
print(S)


print(input().replace('?', 'D'))


A = input()
moji = A.replace('?', 'D')
print(moji)


s = input()
s2 = s.replace('?', 'D')
print(s2)


s = input()
s = s.replace('?', 'D')
print(s)


t = input()
n = len(t)
print(t.replace('?', 'D'))


t = input()
for i in t:
	print('P' if i == 'P' else 'D', end='')


t = input()
s = t.replace('?', 'D')
print(s, end='')


T = input().strip()
print(T.replace('?', 'D'))


t = input().strip()
print(t.replace('?', 'D'))


a = input()
k = a.replace('?', 'D')
print(k)


a = str(input())
a = a.replace('?', 'D')
print(a)


H = input()
print(H.replace('?', 'D'))


s = input()
s = s.translate(str.maketrans({'?': 'D'}))
print(s)


t = str(input())
rt = t.replace('?', 'D')
print(rt)


t = input()
ts = t.replace('?', 'D')
print(ts)


T = input()
ans = T.replace('?', 'D')
print(ans)


T = input()
S = T.replace('?', 'D')
print(S)


t = input()
ans = t.translate(str.maketrans({'?': 'D'}))
print(ans)


S = input()
S2 = S.replace('?', 'D')
print(S2)


T = input()
T2 = T.replace('?', 'D')
print(T2)


T = input()
TT = T.translate(str.maketrans({'?': 'D'}))
print(TT)


data = input()
data_rep = data.replace('?', 'D')
print(data_rep)


S = input()
print(S.replace('?', 'D', len(S)))


word = input().replace('?', 'D')
print(word)


T = input()
u = T.translate(str.maketrans({'?': 'D'}))
print(u)


T = input()
_T = T.replace('?', 'D')
print(_T)


t = input()
tmp = t.replace('?', 'D')
print(tmp)


T = input()
U = T.replace('?', 'D')
print(U)


import re
txt = input()
s = re.sub('[?]', 'D', txt)
print(s)


T = input()
X = len(T)
A = T.replace('?', 'D')
print(A)


word = input().rstrip()
print(word.replace('?', 'D'))


import math
t = input()
t = t.replace('?', 'D')
print(t)


t = list(input())
t = ''.join(t)
t = t.replace('?', 'D')
print(t)


S = input()
a = S.replace('?', 'D')
print(a)


T = input()
T = ['D' if c == '?' else c for c in T]
print(*T, sep='')


t = input()
re_t = t.replace('?', 'D')
print(re_t)


a = input()
b = a.replace('?', 'D')
print(b)


T = input()
y = T.replace('?', 'D')
print(y)


t = input()
tt = t.replace('?', 'D')
print(tt)


import sys
T = input()
newT = T.replace('?', 'D')
print(newT)


s = input().strip()
print(s.replace('?', 'D', len(s)))


T = input()
trade = T.replace('?', 'D')
print(trade)


x = input()
print(x.replace('?', 'D'))


PD = input()
print(PD.replace('?', 'D'))


print(open(0).read().replace('?', 'D'))


T = input()
T1 = T.translate(str.maketrans({'?': 'D'}))
print(T1)


T = input()
ans_T = T.replace('?', 'D')
print(ans_T)


pd = input()
pd = pd.replace('?', 'D')
print(pd)


char = input()
print(char.replace('?', 'D'))


ln = input()
ln1 = ln.replace('?', 'D')
print(ln1)


T = input()
s = T.replace('?', 'D')
print(s)


t = input()
check = False
print(t.replace('?', 'D'))


s = input()
a1 = s.replace('?', 'D')
print(a1)


T = input()
result = T.replace('?', 'D')
print(result)


t = input()
s = [i if i != '?' else 'D' for i in t]
print(''.join(s))


A = input()
print(A.replace('?', 'D'))


t = input()
dt = t.replace('?', 'D')
print(dt)


S = input()
print(S.translate(str.maketrans({'?': 'D'})))


s = input()
while '?' in s:
	s = s.replace('?', 'D')
print(s)


T = input()
tmp = T.replace('?', 'D')
print(tmp)


a = ['D' if i == '?' else i for i in input()]
print(''.join(a))


t = input()
x = t.replace('?', 'D')
print(x)


s = input()
ans = s.replace('?', 'D')
print(ans)


print(''.join(['D' if c == '?' else c for c in input()]))


t = input()
t2 = t.replace('?', 'D')
print(t2)


t = input()
t_replace = t.replace('?', 'D')
print(t_replace)


T = input()
G = T.replace('?', 'D')
ans = G.count('D')
print(G)


line = input()
print(line.replace('?', 'D'))


s = str(input())
sl = s.replace('?', 'D')
print(sl)


import re
print(re.sub('\\?', 'D', input()))


s = input()
pd = s.replace('?', 'D')
print(pd)


T = input()
N = len(T)
print(T.replace('?', 'D'))


T = input()
print(''.join(['D' if s == '?' else s for s in T]))


T = input()
l = len(T)
print(T.replace('?', 'D'))


input_ = input()
ans = input_.replace('?', 'D')
print(ans)


def main():
	t = input()
	print(t.replace('?', 'D'))
main()


t = input()
a = t.replace('?', 'D')
print(a)


s = input()
n = len(s)
s = s.replace('?', 'D')
print(s)


t = input()
n = len(t)
count = 0
s = t.replace('?', 'D')
print(s)


sl = input()
print(sl.replace('?', 'D'))


T = input()
r = T.replace('?', 'D')
print(r)


T = input()
T = T.replace('?', 'D')
print(''.join(T))


moji = input()
moji = moji.replace('?', 'D')
print(moji)


data = input()
result = data.replace('?', 'D')
print(result)