Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
csum = list(np.cumsum(a_ls))
ans = 0

for start in range(1,n):
    for end in range(start, n):
        if csum[end] - csum[start-1] == 0:
            ans += 1
for i in range(n):
    if csum[i] == 0:
        ans += 1
print(ans)



Fixed submission:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a_ls = list(map(int, input().split()))
a_csum = [0] * n
now = 0
for i in range(n):
    now += a_ls[i]
    a_csum[i] = now
a_csum.append(0)
a_csum.sort()
ans = 0
now = 0
for i in range(n):
    if a_csum[i] == a_csum[i+1]:
        now += 1
    else:
        if now > 0:
            ans += combinations_count(now+1,2)
        now = 0
if now > 0:
    ans += combinations_count(now+1,2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
csum = list(np.cumsum(a_ls))
ans = 0

for start in range(1,n):
    for end in range(start, n):
        if csum[end] - csum[start-1] == 0:
            ans += 1
for i in range(n):
    if csum[i] == 0:
        ans += 1
print(ans)



Fixed submission:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a_ls = list(map(int, input().split()))
a_csum = [0] * n
now = 0
for i in range(n):
    now += a_ls[i]
    a_csum[i] = now
a_csum.append(0)
a_csum.sort()
ans = 0
now = 0
for i in range(n):
    if a_csum[i] == a_csum[i+1]:
        now += 1
    else:
        if now > 0:
            ans += combinations_count(now+1,2)
        now = 0
if now > 0:
    ans += combinations_count(now+1,2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
x_ls = list(map(int, input().split()))

sorted_x = sorted(x_ls)
bigger = sorted_x[n//2]
smaller = sorted_x[n//2 - 1]
for i in range(n):
    target_ind = sorted_x.index(x_ls[i])
    if target_ind <= n // 2 - 1:
        ans = bigger
    else:
        ans = smaller
    print(ans)


Fixed submission:
n = int(input())
x_ls = list(map(int, input().split()))

sorted_x = sorted(x_ls)
bigger = sorted_x[n//2]
smaller = sorted_x[n//2 - 1]

# 含まれてるならそのインデックス 、含まれてないなら-1を返す
def binary_search(l, item):
    left = 0
    right = len(l) - 1
    while left <= right:
        mid  = (left + right) // 2
        if l[mid] == item:
            return mid
        elif l[mid] < item:
            left = mid + 1
        else:
            right = mid - 1
    return -1

for i in range(n):
    target_ind = binary_search(sorted_x, x_ls[i])
    if target_ind <= n // 2 - 1:
        ans = bigger
    else:
        ans = smaller
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for start in range(n_node):
    for end in range(n_node):
        for stop in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)


Fixed submission:
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for stop in range(n_node):
    for start in range(n_node):
        for end in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)

Buggy python submission (verdict: Runtime Error):
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_edge for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for start in range(n_node):
    for end in range(n_node):
        for stop in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)


Fixed submission:
from itertools import permutations
n_node, n_edge, R = map(int,input().split())
r_ls = list(map(int,input().split()))
for i in range(R):
    r_ls[i] -= 1
ad_mat = [[float('inf')]*n_node for _ in range(n_node)]
for i in range(n_node):
    ad_mat[i][i] = 0
for i in range(n_edge):
    a,b,c = map(int,input().split())
    ad_mat[a-1][b-1] = c
    ad_mat[b-1][a-1] = c

# ワーシャルフロイド
for stop in range(n_node):
    for start in range(n_node):
        for end in range(n_node):
            ad_mat[start][end] = min(ad_mat[start][end],ad_mat[start][stop]+ad_mat[stop][end])

ans = float('inf')
for path in permutations(r_ls):
    cost = 0
    for i in range(R-1):
        cost += ad_mat[path[i]][path[i+1]]
    ans = min(ans,cost)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
H,W = map(int,input().split())
n = int(input())
a_ls = list(map(int, input().split()))
color_q = deque()
for color, times in enumerate(a_ls,1):
    for _ in range(times):
        color_q.append(color)
ans_mat = [[0] * W for _ in range(W)]
for y in range(H):
    for x in range(W):
        ans_mat[y][x] = color_q.popleft()
for i,y in enumerate(range(H)):
    ans_ls = ans_mat[y]
    if i % 2 == 1:
        ans_ls = ans_ls[::-1]
    ans_ls = list(map(str,ans_ls))
    print(' '.join(ans_ls))

Fixed submission:
from collections import deque
H,W = map(int,input().split())
n = int(input())
a_ls = list(map(int, input().split()))
color_q = deque()
for color, times in enumerate(a_ls,1):
    for _ in range(times):
        color_q.append(color)
ans_mat = [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        ans_mat[y][x] = color_q.popleft()
for i,y in enumerate(range(H)):
    ans_ls = ans_mat[y]
    if i % 2 == 1:
        ans_ls = ans_ls[::-1]
    ans_ls = list(map(str,ans_ls))
    print(' '.join(ans_ls))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
if abs(n-m) >= 2:
    num_dm = 0
elif abs(n-m) == 1:
    num_dm = 1
else:
    num_dm = 2
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
d_comb_num = factorial(n)
m_comb_num = factorial(m)
ans = num_dm * d_comb_num * m_comb_num
print(ans)

Fixed submission:
import math
mod = 1000000007

n,m = map(int,input().split())
if abs(n-m) >= 2:
    num_dm = 0
elif abs(n-m) == 1:
    num_dm = 1
else:
    num_dm = 2
d_comb_num = math.factorial(n) % mod
m_comb_num = math.factorial(m) % mod
ans = num_dm * d_comb_num * m_comb_num
ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np 
n = int(input())
size_ls = list(map(int, input().split()))
size_ls.sort()
csum_size = list(np.cumsum(size_ls))

# とりあえず、与えられたインデックスの生き物が全部食べることをできるか返す関数
def isOK(start):
    res = True
    for i in range(start, n-1):
            if not 2 * csum_size[i] >= size_ls[i + 1]:
                res = False
                break
    return res

ans = 1
for i in range(n-1):
    if isOK(i):
        ans += 1
print(ans)

Fixed submission:
import numpy as np 
n = int(input())
size_ls = list(map(int, input().split()))
size_ls.sort()
csum_size = list(np.cumsum(size_ls))

can_ls = [0] * n
can_ls[-1] = 1
for i in range(n-1):
    if 2 * csum_size[i] >= size_ls[i+1]:
        can_ls[i] = 1
ans = 0
for i in range(n-1,-1,-1):
    if can_ls[i] != 1:
        break
    ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np 
n = int(input())
size_ls = list(map(int, input().split()))
size_ls.sort()
csum_size = list(np.cumsum(size_ls))

# とりあえず、与えられたインデックスの生き物が全部食べることをできるか返す関数
def isOK(start):
    res = True
    for i in range(start, n-1):
            if not 2 * csum_size[i] >= size_ls[i + 1]:
                res = False
                break
    return res

ans = 1
for i in range(n-1):
    if isOK(i):
        ans += 1
print(ans)

Fixed submission:
import numpy as np 
n = int(input())
size_ls = list(map(int, input().split()))
size_ls.sort()
csum_size = list(np.cumsum(size_ls))

can_ls = [0] * n
can_ls[-1] = 1
for i in range(n-1):
    if 2 * csum_size[i] >= size_ls[i+1]:
        can_ls[i] = 1
ans = 0
for i in range(n-1,-1,-1):
    if can_ls[i] != 1:
        break
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
s = n
c = m
while True:
    if s * 2 < c:
        s += 1
        c -= 2
    else:
        break
ans = min(s, c//2)
print(ans)

Fixed submission:
n,m = map(int,input().split())
s = n
c = m
if 2 * s < c:
    add = (c - 2*s) // 4
    ans = s + add
elif 2 * s == c:
    ans = s
else:
    ans = c // 2
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2000)
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    # 上のループを通した後にtempが1じゃなかったら、だけど、nが素数以外にそんなケースある？
    if temp!=1:
        arr.append([temp, 1])
    
    # 素数だったときの処理
    if arr == []:
        arr.append([n,1])

    return arr

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
F = factorial(n)
factor_ls = factorization(F)
ls = [factor[1] for factor in factor_ls]
num_factor = 1
for i in ls:
    num_factor *= (i + 1)
print(num_factor % (10**9 + 7))


Fixed submission:
mod = 1000000000 + 7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

n = int(input())
dat = [0] * 2000 # 約数として求められたある数の合計

# N! の各要素の素因数分解をする
res = 1
for i in range(1, n + 1):
    d = factorization(i)
    for j in range(len(d)):
        dat[d[j][0]] += d[j][1]

for i in range(2, n + 1):
    res *= (dat[i] + 1)
    res %= mod

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)

Fixed submission:
N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)

Buggy python submission (verdict: Runtime Error):
N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[1][1][card_ls[0]] = 1
dp[1][0][0] = 1
for i in range(1,N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)

Fixed submission:
N,ave = map(int,input().split())
card_ls = list(map(int, input().split()))
#dp[i+1][n][s] := i番目までのカード(0idx)からn枚使って合計がsとなるパターンの数
dp = [[[0]*(ave*N+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for n in range(N):
        for s in range(ave*N+1):
            # i番目を新しく使う
            if s+card_ls[i] < ave*N+1:
                dp[i+1][n+1][s+card_ls[i]] += dp[i][n][s]
            # i番目を使わない
            dp[i+1][n][s] += dp[i][n][s]

#print(dp)
ans = 0
for n in range(1,N+1):
    ans += dp[N][n][n*ave]
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ls = [0] * N
for i in range(N):
    a = int(input())
    ls[i] = a

def return_ans(ls):
    ans = 0
    n = len(ls)
    if n > 1:
        for i in range(n-1):
            if ls[i] % 2 == 1 and ls[i+1] > 0:
                ls[i] += 1
                ls[i+1] -= 1
            ans += ls[i] // 2
    ans += ls[-1]//2
    return ans

now_ls = []
ans = 0
for i in range(N):
    if ls[i] != 0:
        now_ls.append(ls[i])
    else:
        ans += return_ans(now_ls)
        now_ls = []
if now_ls:
    ans += return_ans(now_ls)

print(ans)


Fixed submission:
n = int(input())
ls = [0] * n
for i in range(n):
    a = int(input())
    ls[i] = a

ans = 0
for i in range(n-1):
    if ls[i] % 2 == 1 and ls[i+1] > 0:
        ls[i] += 1
        ls[i+1] -= 1
    ans += ls[i] // 2
ans += ls[-1] // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys

def main():
    #an+1=(10~n)*7+an
    K=int(input())
    if K%2==0:
        print(-1)
        sys.exit()
    n=0
    a=7
    while True:
        if a%K==0:
            break
        n+=1
        a=(a+(pow(10,n,K)*7))%K
    print(n+1)

if __name__=="__main__":
    main()

Fixed submission:
import math
import sys

def main():
    #an+1=(10~n)*7+an
    K=int(input())

    if K%2==0:
        print(-1)
        sys.exit()
    elif K%5==0:
        print(-1)
        sys.exit()
    n=0
    a=7
    while True:
        if a%K==0:
            break
        n+=1
        a=(a+(pow(10,n,K)*7))%K
    print(n+1)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys

def main():
    N=int(input())
    A=list(map(int,input().split()))

    A.sort(reversed=True)

    res=0
    res+=A[0]
    res+=A[1]*(N-2)
    print(res)

if __name__=="__main__":
    main()

Fixed submission:
def main():
    N=int(input())
    A=list(map(int,input().split()))

    A.sort(reverse=True)

    res=A[0]

    counter=1

    while counter<=N-2:
        index = (counter + 1) // 2
        res+=A[index]
        counter+=1

    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
import math

def main():
    X=int(input())

    res=0
    vec=np.array([1,0])
    rot=np.array([[math.cos(math.radians(X)),-1*math.sin(math.radians(X))],[math.sin(math.radians(X)),math.cos(math.radians(X))]])
    pos=np.array([0,0])

    pos=pos+vec
    vec=np.dot(rot,vec)
    res+=1
    while abs(pos[0])>=0.001 or abs(pos[1])>=0.001:
        pos=pos+vec
        vec=np.dot(rot,vec)
        res+=1
    print(res)

if __name__=="__main__":
    main()

Fixed submission:
import numpy as np
import math

def main():
    X=int(input())

    res=0
    vec=np.array([1,0])
    rot=np.array([[math.cos(math.radians(X)),-1*math.sin(math.radians(X))],[math.sin(math.radians(X)),math.cos(math.radians(X))]])
    pos=np.array([0,0])

    pos=pos+vec
    vec=np.dot(rot,vec)
    res+=1
    while abs(pos[0])>=0.001 or abs(pos[1])>=0.001:
        pos=pos+vec
        vec=np.dot(rot,vec)
        res+=1
    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
C:\Users\kouya\Anaconda3\python.exe C:/Users/kouya/pywork/atcoder/past/Contest170.py
2 100
No

Process finished with exit code 0


Fixed submission:
import sys

def main():
    X,Y=map(int,input().split())
    crane=(Y-2*X)/2
    if crane!=int(crane):
        print("No")
        sys.exit()
    turtle=X-crane
    if crane>=0 and turtle>=0:
        print("Yes")
    else:
        print("No")

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))


    for _ in range(K):
        counter=[0 for _ in range(N)]

        for i in range(len(A)):
            left=max(0,i-A[i])
            right=min(N-1,i+A[i])
            counter[left]+=1
            if right+1<N:
                counter[right+1]-=1
        for i in range(len(counter)-1):
            counter[i+1]+=counter[i]

        if counter==A:
            break
        else:
            A=counter

    for i in range(N):
        if i!=N-1:
            print(str(A[i])+" ",end="")
        else:
            print(A[i])

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))


    for _ in range(K):
        counter=[0 for _ in range(N)]

        for i in range(len(A)):
            left=max(0,i-A[i])
            right=min(N-1,i+A[i])
            counter[left]+=1
            if right+1<N:
                counter[right+1]-=1
        for i in range(len(counter)-1):
            counter[i+1]+=counter[i]

        if counter==A:
            break
        else:
            A=counter

    for i in range(N):
        if i!=N-1:
            print(str(A[i])+" ",end="")
        else:
            print(A[i])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import numpy as np


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))


    for _ in range(K):
        counter=[0 for _ in range(N)]

        for i in range(len(A)):
            left=max(0,i-A[i])
            right=min(N-1,i+A[i])
            counter[left]+=1
            if right+1<N:
                counter[right+1]-=1
        for i in range(len(counter)-1):
            counter[i+1]+=counter[i]

        if counter==A:
            break
        else:
            A=counter

    print(A)

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))


    for _ in range(K):
        counter=[0 for _ in range(N)]

        for i in range(len(A)):
            left=max(0,i-A[i])
            right=min(N-1,i+A[i])
            counter[left]+=1
            if right+1<N:
                counter[right+1]-=1
        for i in range(len(counter)-1):
            counter[i+1]+=counter[i]

        if counter==A:
            break
        else:
            A=counter

    for i in range(N):
        if i!=N-1:
            print(str(A[i])+" ",end="")
        else:
            print(A[i])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    S=input()
    res=""

    for i in range(len(S)):
        if S[i]=="?":
            if i==0:
                if S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
            elif i==len(S)-1:
                res+="D"
            else:
                if res[i-1]=="P":
                    res+="D"
                elif S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
        else:
            res+=S[i]
    print(res)

if __name__=="__main__":
    main()


Fixed submission:
def main():
    S=input()
    res=""

    for i in range(len(S)):
        if S[i]=="?":
            if len(S)==1:
                res+="D"
                continue
            if i==0:
                if S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
            elif i==len(S)-1:
                res+="D"
            else:
                if res[i-1]=="P":
                    res+="D"
                elif S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
        else:
            res+=S[i]
    print(res)

if __name__=="__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    S=input()
    res=""

    for i in range(len(S)):
        if S[i]=="?":
            if i==0:
                if S[i+1]=="?":
                    res+="P"
                else:
                    res=+"D"
            elif i==len(S)-1:
                res+="D"
            else:
                if res[i-1]=="P":
                    res+="D"
                elif S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
        else:
            res+=S[i]
    print(res)

if __name__=="__main__":
    main()


Fixed submission:
def main():
    S=input()
    res=""

    for i in range(len(S)):
        if S[i]=="?":
            if len(S)==1:
                res+="D"
                continue
            if i==0:
                if S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
            elif i==len(S)-1:
                res+="D"
            else:
                if res[i-1]=="P":
                    res+="D"
                elif S[i+1]=="?":
                    res+="P"
                else:
                    res+="D"
        else:
            res+=S[i]
    print(res)

if __name__=="__main__":
    main()