Harryxun/stf_run huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n, m = map(int, input().split())
uf = UnionFind(n)
 
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
print(uf.group_count()-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = set()

for i in range(n):
    ans.add(uf.find(i))

print(len(ans)-1)
import sys
from io import StringIO
import unittest

import math

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = (10**5)*2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x = x%mod #
        n //= 2

    return K * x

def resolve():

    n,a,b = list(map(int,input().strip().split()))

    ptn = pow_k(2,n)
    ptn -= 1


    comba=cmb(n,a,mod)
    combb=cmb(n,b,mod)

    ptn -= (comba+combb)
    ptn = ptn%mod

    print(ptn)

    return 

resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest
import math

mod = 10**9+7

def pow_mod(a, b, mod):
    x = 1
    while b > 0:
        if b & 1:
            x = (x*a)%mod
        a = (a**2)%mod
        b //= 2
 
    return x

def modinv(a, mod):
    return pow_mod(a, mod-2, mod)

def comb(n,r,mod):
    combsum=1
    for i in range(n-r+1,n+1):
        combsum = (combsum * i)%mod

    for i in range(1,r+1):
        combsum = (combsum * inv[i])%mod

    return combsum

n,a,b = list(map(int,input().strip().split()))

a=min([a,n-a])
b=min([b,n-b])

maxab=max([a,b])

inv=[modinv(i,mod) for i in range(0,maxab+2)]

def resolve():

    ptn = pow_mod(2,n,mod)
    ptn -= 1

    comba=comb(n,a,mod)
    combb=comb(n,b,mod)

    ptn = (ptn-comba-combb)%mod

    print(ptn)

    return 

resolve()
n=int(input())
diez=10*n+10
if(1<=n<=10000):
    if(n!=10):
        print(diez-n)
    else:
        print(n+99)


### FIXED CODE ###

from sys import stdin

def main():
    s = stdin.readline().strip()
    print(chr(ord(s)+1))

main()
N = int(input())
A = []
for i in range(a):
    x, l = map(int, input().split())
    A.append([x+l, x-l])
A.sort()
ans = 1
check1 = A[0]
for i in range(1, N):
    check2 = A[i]
    if check1[0] <= check2[1]:
        ans += 1
        check1 = check2
print(ans)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    x, l = map(int, input().split())
    A.append([x+l, x-l])
A.sort()
ans = 1
check1 = A[0]
for i in range(1, N):
    check2 = A[i]
    if check1[0] <= check2[1]:
        ans += 1
        check1 = check2
print(ans)
a=int(input())
b=int(input())

if (a+b)%2==0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

a,b=map(int,input().split())

if (a*b)%2==0:
  print('Even')
else:
  print('Odd')
X,Y = map(int,input())
ans = 0
while X <= Y:
	ans += 1
	X *= 2
print(ans)

### FIXED CODE ###

X,Y = map(int,input().split())
ans = 0
while X <= Y:
	ans += 1
	X *= 2
print(ans)
A,B,C=(int,input().split()))
print(C-A+B)

### FIXED CODE ###

A,B,C = map(int,input().split())
X = C - A + B
if X < 0:
    X = 0
print(X)
# 0-1 Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))

DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(W, w-1, -1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1][-1])

### FIXED CODE ###

# 0-1 Knapsack Problem
N, W = [int(x) for x in input().split()]
items = []
for i in range(N):
    items.append(tuple(int(x) for x in input().split()))

DP = [0] * (W+1)
for i in range(N):
    v, w = items[i]
    for j in range(W, w-1, -1):
        DP[j] = max(DP[j], v + DP[j-w])

print(DP[-1])
intA = int(input())
intX = int(input())

if 0<=intA and intA<=9 and 0<=intX and intX<=9:
	if intX<intA:
		print(0)
	else:
		print(10)

### FIXED CODE ###

X,A = list(map(int,input().split()))
print(0 if X<A else 10)
# -*- coding:utf-8 -*-

def solve():
    A, B = list(map(int, input().split()))
    if A > B:
        print("GREATER")
    elif A < B:
        print("LESS")
    else:
        print("EQUAL")
        

if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    A = int(input())
    B = int(input())
    if A > B:
        print("GREATER")
    elif A < B:
        print("LESS")
    else:
        print("EQUAL")


if __name__ == "__main__":
    solve()
a, b = map(int, input().split())
if (a < b):
	print(???a>b???)
elif (a > b):
	print(???a>b???)
else:
	print(???a=b???)

### FIXED CODE ###

a, b = map(int, input().split())
if (a > b):
	print("a > b")
elif (a < b):
	print("a < b")
elif (a == b):
	print("a == b")
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

r = math.floor(math.log2(L+1))
M = 0
edge = []
for i in range(r):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(r)[::-1]:
    if L-2**i >= 2**r:
        edge.append([i,r,L-2**i])
        M += 1
        L -= 2**i

print(r+1,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

N = math.floor(math.log2(L))+1
M = 0
edge = []
for i in range(N-1):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(N-1)[::-1]:
    if L-2**i >= 2**(N-1):
        edge.append([i,N-1,L-2**i])
        M += 1
        L -= 2**i

print(N,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])
N = int(input())
S = input()
S = list(S)
count = 0
for i in range(N-1):
    if S[i] == "A":
        if S[i+1] == "B":
            if S[i+2] == "C":
                count+=1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
S = list(S)
count = 0
for i in range(N-2):
    if S[i] == "A":
        if S[i+1] == "B":
            if S[i+2] == "C":
                count+=1
print(count)
h,m,s=0,0,int(input())
while s >= 3600:
    s-=3600
    h+=1
while s >= 60:
    s-=60
    m+=1
print(h+':'+m+':'+s)

### FIXED CODE ###

from datetime import timedelta
print(':'.join(list(map(str,map(int,str(timedelta(seconds=int(input()))).split(':'))))))
N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not m:
        ans = max(ans, d)

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
A.sort()

S = sum(A)
candidates = []
for i in range(1, int(S**0.5)+1):
    if S%i:continue
    a, b = i, S//i
    
    candidates.append(a)
    if a!=b:
        candidates.append(b)
candidates.sort()

ans = 0
for d in candidates:
    rems = []
    rems_size, rems_sum = 0, 0

    for i in A:
        if i%d:
            rems.append(i%d)
            rems_size += 1
            rems_sum += i%d

    rems.sort()

    a = 0
    for i, j in enumerate(rems[:-1], start=1):
        a += j
        b = d*(rems_size-i)-(rems_sum-a)
        if max(a, b)<=K:
            ans = max(ans, d)
    if not rems:
        ans = max(ans, d)

print(ans)
k, x = map(int, input().split())
for i in range(max(1, x - 3), x + 4, 1):
  preint(i)

### FIXED CODE ###

k, x = map(int, input().split())
for i in range(x - k + 1, x + k):
  print(i, end = " ")
h,w = list(map(int,input()))
for _ in range(h):
  s = input()
  print(s)
  print(s)


### FIXED CODE ###

h,w = list(map(int,input().split()))
for _ in range(h):
  s = input()
  print(s)
  print(s)
N , X = (map(int , input().split()))
x = list(map(int , input().split()))
x.sort()
ans_list = [x[i+1] - x[i] for i in range(0,len(x)-1)]
if X == 1:
    print(x[0]-X)
else:
    from fractions import gcd
    print(gcd(ans_list[0], ans_list[1]))

### FIXED CODE ###

from fractions import gcd
N , X = (map(int , input().split()))
x = list(map(int , input().split()))
ans = 0
for i in x:
    ans = gcd(ans , abs(X-i))
print(ans)
def cmb(n, k, mod, fac, infac):
  k = min(k,n-k)
  return fac[n] * infac[k] * infac[n-k] % mod

def tables(mod, n):
  fac = [1, 1] 
  infac = [1, 1] 
  inverse = [0, 1] 
  for i in range(2, n+1):
    fac.append((fac[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    infac.append((infac[-1] * inverse[-1]) % mod)
  return fac,infac

X,Y = map(int, input().split())

if X > Y:
  X, Y = Y, X

move = X + Y

if move % 3 != 0:
  print(0)
else:
  total = move // 3
  n = X - total
  
  if n > 0:
    print(0)
  else:
    MOD = 10 ** 9 + 7
    fac, infac = tables(MOD, total)
    ans = cmb(total, n, MOD, fac, infac)
    
    print(ans)

### FIXED CODE ###

def cmb(n, k, mod, fac, infac):
  k = min(k,n-k)
  return fac[n] * infac[k] * infac[n-k] % mod

def tables(mod, n):
  fac = [1, 1] 
  infac = [1, 1] 
  inverse = [0, 1] 
  for i in range(2, n+1):
    fac.append((fac[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    infac.append((infac[-1] * inverse[-1]) % mod)
  return fac,infac

X,Y = map(int, input().split())

if X > Y:
  X, Y = Y, X

move = X + Y

if move % 3 != 0:
  print(0)
else:
  total = move // 3
  n = X - total
  
  if n < 0:
    print(0)
    
  else:
    MOD = 10 ** 9 + 7
    fac, infac = tables(MOD, total)
    ans = cmb(total, n, MOD, fac, infac)
    
    print(ans)
from scipy.special import comb

n, a, b = map(int, input().split())
MOD = 10**9+7


all_c = pow(2, n, MOD)-1
a_c = 1
b_c = 1
for i in range(n-a+1, n+1):
    a_c *= i
    a_c %= MOD
for i in range(1, a+1):
    a_c *= pow(i, MOD-2, MOD)
    a_c %= MOD
for i in range(n-b+1, n+1):
    b_c *= i
    b_c %= MOD
for i in range(1, b+1):
    b_c *= pow(i, MOD-2, MOD)
    b_c %= MOD

ans = (all_c - a_c - b_c) % MOD
print(ans)


### FIXED CODE ###

n, a, b = map(int, input().split())
MOD = 10**9+7


all_c = pow(2, n, MOD)-1
a_c = 1
b_c = 1
for i in range(n-a+1, n+1):
    a_c *= i
    a_c %= MOD
for i in range(1, a+1):
    a_c *= pow(i, MOD-2, MOD)
    a_c %= MOD
for i in range(n-b+1, n+1):
    b_c *= i
    b_c %= MOD
for i in range(1, b+1):
    b_c *= pow(i, MOD-2, MOD)
    b_c %= MOD

ans = (all_c - a_c - b_c) % MOD
print(ans)
import sys
import numpy as np

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.append(N+1)
a = np.array(a)
sum_move = 1
fact = [-1] * (N+1)
fact = np.array(fact)
fact[0] = 1


def factorial(num, fact):
    if fact[num] > 0:
        return fact[num]
    else:
        fact[num] = factorial(num-1, fact) * num
        return fact[num]


step_begin = 0
for i in range(M+1):
    tmp_sum = 0
    step_end = a[i] - 1
    step_num = step_end - step_begin
    for j in range(step_num//2 + 1):
        tmp_sum += factorial(step_num - j, fact) \
            // factorial(j, fact) // factorial(step_num - 2 * j, fact)
    if tmp_sum != 0:
        sum_move *= tmp_sum
    else:
        sum_move = 0
        break
    step_begin = step_end + 2

print(sum_move % 1000000007)


### FIXED CODE ###

N, M = map(int, input().split())
oks = [True] * (N+1)
a = [int(input()) for _ in range(M)]
for i in a:
    oks[i] = False

dp = [0] * (N+1)
dp[0] = 1
for i in range(N+1):
    for j in range(i+1, min(i+2, N)+1):
        if oks[j]:
            dp[j] += dp[i]
            dp[j] %= int(1e9+7)


print(dp[N])
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if mac(a,b,c,d,e)-min(a,b,c,d,e)<=k:
    print("Yay!")
else:
    print(":(")


### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if max(a,b,c,d,e)-min(a,b,c,d,e)<=k:
    print("Yay!")
else:
    print(":(")
n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
h=[::-1]
if k!=0:
  for i in range(k):
    h[i]=0

  
print(sum(h))


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort()
h=h[::-1]

if k>=n:
  print(0)
  
elif k!=0:
  for i in range(k):
    h[i]=0
  print(sum(h))

else:
  print(sum(h))
from math import sqrt


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    divisors.sort()
    return divisors


if __name__ == "__main__":
    N, P = map(int, input().split())

    A = Calc_Divisors(P)

    ans = 1
    for i in A:
        tmp = P % (i ** N)
        if tmp == 0:
            ans = i

    print(ans)


### FIXED CODE ###

from math import sqrt


def Calc_Divisors(num):
    divisors = []
    for i in range(1, int(sqrt(num)) + 1):
        if num % i == 0:
            divisors.append(i)
            if i != num // i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

if __name__ == "__main__":
    N, P = map(int, input().split())

    A = Calc_Divisors(P)

    ans = 1
    for i in A:
        tmp = P % (pow(i, N))
        if N > 40:
            print(ans)
            exit()
        if pow(i, N) > P:
            print(ans)
            exit()
        if tmp == 0:
            ans = i

    print(ans)
from itertools import zip_longest


def main():
    _, *a = map(int, open(0))
    a = sorted(a, reverse=True)
    print(sum(i - j for i, j in zip_longest(*[iter(a)]*2, fillvalue=0)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from itertools import zip_longest

def main():
    n, *a = map(int, open(0).read().split())
    a = reversed(sorted(a))
    res = sum(a - b for a, b in zip_longest(*[iter(a)]*2, fillvalue=0))
    print(res)


if __name__ == "__main__":
    main()
x = int(input())
if x = 0:
  print(1)
else:
  print(0)

### FIXED CODE ###

x = int(input())
if x == 1:
  print(0)
else:
  print(1)
n=int(input(n))
a=list(map(int,input().split()))
c=0
for i in range(n):
    if i==a[a[i]-1]:
        c+=1
        a[i]=n+1
print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if i+1==a[a[i]-1]:
        c+=1
        a[i]=n+2
print(c)
import sys

nums = []


for line in sys.stdin:
    nums.append(line)

for i in range(len(nums)):
    input_line = nums[i].split(" ")
    a = int(input_line[0])
    b = int(input_line[1])


    #??¬?´???°?????????
    common_div = []

    #?????§??¬?´???°
    if a < b:
        last_num = a
    else:
        last_num = b

    for j in range(1,last_num-1):
        if a%j == 0 and b%j == 0:
            #a???b???j??§???????????¨???
            common_div.append(j)
    
    max_common_div = common_div[len(common_div)-1]
    min_common_mpl = int((a * b)/max_common_div)

    print(str(max_common_div) + " " + str(min_common_mpl))

    

### FIXED CODE ###

import sys
 
nums = []
 
 
for line in sys.stdin:
    nums.append(line)
 
for i in range(len(nums)):
    input_line = nums[i].split(" ")
    a = int(input_line[0])
    b = int(input_line[1])
 
    if a > b:
        num_bigger = a
        num_smaller = b
    else:
        num_bigger = b
        num_smaller = a

    r = 1   #?????????
    while r > 0:
        r = num_bigger % num_smaller
        num_bigger = num_smaller
        num_smaller = r

    max_common_div = num_bigger
    min_common_mpl = int((a * b)/max_common_div)
 
    print(str(max_common_div) + " " + str(min_common_mpl))
import math
n=int(input())
noso=[]
count=0
if n==1:
    count=0
elif sosu(n)==1:
        count=1
else:
    for x in range(2,int(n/2)+2):
        if x>n:
            break
        if x in noso:
            pass
        elif x<=10:
            xx=x
            while n%xx==0:
                noso.append(xx)
                count+=1
                n=n/xx
                xx=xx*x
        elif x>11:
            xx=x
            while n%xx==0:
                noso.append(xx)
                count+=1
                n=n/x
                xx=xx*x
print(count)

### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
n=int(input())
if n==1:
    ans=0
else:
    a=prime_factorize(n)
    if a==[]:
        ans=1
    else:
        ans=0
        xzen=a[0]
        count=1
        ans+=1
        for x in range(1,len(a)):
            if xzen==a[x]:
                count+=1
                if count==3 or count==6 or count==10 or count==15 or count==21 or count==28 or count==36:
                    ans+=1
            else:
                xzen=a[x]
                count=1
                ans+=1
print(ans)
l = input()
if l<1200:
    print("ABC")
elif l<2800
    print("ARC")
else :
    print("AGC")

### FIXED CODE ###

l = int(input())
if l<1200:
    print("ABC")
elif l<2800:
    print("ARC")
else :
    print("AGC")
a = input()
ans = upper(a)
if a == ans:
  print("A")
else:
  print("a") 

### FIXED CODE ###

a = input()
ans = a.upper()
if a == ans:
  print("A")
else:
  print("a")
import math

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
    
a,b=list(map(int,input().strip().split()))
c=gcd(a,b)
e=c
d=0
for i in range(2,math.ceil(math.sqrt(e)+2)):
    if c%i==0:
        d=d+1
        c=c//i
print(d+1)

### FIXED CODE ###

n=int(input())
if n%2==0:
    print(0.5)
else:
    print((n//2+1)/n)
from sys import stdin
from functools import reduce 

# 標準入力から読み込み
inputs = [list(map(int, input().split())) for _ in range(2)]
inputs = inputs[1]

if (0 in inputs):
  output = 0
else:
  output = reduce((lambda x, y: -1 if (x * y) <= 1e18 or x < 0 or y < 0  else (X * y)), inputs)

print(output)

### FIXED CODE ###

from sys import stdin
from functools import reduce 

# 標準入力から読み込み
inputs = [list(map(int, input().split())) for _ in range(2)]
inputs = inputs[1]

if (0 in inputs):
  output = 0
else:
  output = reduce((lambda x, y: -1 if (x * y) > 1e18 or x < 0 or y < 0  else (x * y)), inputs)

print(output)
import numpy as np

input_str  = list(input())
count = 0

if input_str[0] == '?':
    if input_str[1] == 'P':
        input_str[0] == 'D'
    else:
        input_str[0] = 'P'

if input_str[-1] == '?':
    input_str[-1] = 'D'


for i in range(1,len(input_str)-1):
    if input_str[i] == '?':
        if input_str[i-1] == 'P':
            input_str[i] = 'D'
        elif input_str[i+1] == 'P':
            input_str[i] = 'D'
        elif input_str[i+1] == '?':
            if input_str[i-1] == 'P':
                input_str[i] = 'D'
            else:
                input_str[i] = 'P'
        elif input_str[i+1] == 'D':
            input_str[i] = 'D'

for i in range(len(input_str)-1):
    if input_str[i] == 'D':
        count = count + 1
    if input_str[i] == 'P' and input_str[i+1] == 'D':
        count = count + 1
if input_str[-1] == 'D':
    count = count + 1
ans = ''.join(input_str)
print(ans)


### FIXED CODE ###

import numpy as np

input_str  = list(input())
count = 0



if len(input_str) == 1:
    input_str[0] = 'D'
else:
    if input_str[0] == '?':
        if input_str[1] == 'P':
            input_str[0] = 'D'
        else:
            input_str[0] = 'P'

    if input_str[-1] == '?':
        input_str[-1] = 'D'

    for i in range(1,len(input_str)-1):
        if input_str[i] == '?':
            if input_str[i-1] == 'P':
                input_str[i] = 'D'
            elif input_str[i+1] == 'D':
                input_str[i] = 'P'
            elif input_str[i+1] == '?':
                if input_str[i-1] == 'P':
                    input_str[i] = 'D'
                else:
                    input_str[i] = 'P'
            else:
                input_str[i] = 'D'

ans = ''.join(input_str)

print(ans)