Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**5)

n, q = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print(tree_value[i])


### FIXED CODE ###

import sys
from queue import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, q = list(map(int, input().split()))

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")
N, K = map(int, input().split())
A = list(map(int, input().split()))

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  a = t_zero.index(t_zero[a] + k)
print(a)

### FIXED CODE ###

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  for _ in range(k):
    a = A[a-1]
print(a)
import sys

input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int,input().split())
    tree[a].append((b,1))
    tree[b].append((a,1))

depth = [None]*(N+1)
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
DFS(1,0,0)

depthN = [None]*(N+1)
def DFSN(v,p,d):
    depthN[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFSN(e[0], v, d + e[1])
DFSN(N,0,0)

black = 0
for i in range(1,N):
    if depth[i] <= depthN[i]:
        black += 1

if black > N/2:
    print("Fennec")
else:
    print("Snuke")



### FIXED CODE ###

import sys
sys.setrecursionlimit(sys.getrecursionlimit()*1000)

input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int,input().split())
    tree[a].append((b,1))
    tree[b].append((a,1))

depth = [None]*(N+1)
def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFS(e[0], v, d + e[1])
DFS(1,0,0)

depthN = [None]*(N+1)
def DFSN(v,p,d):
    depthN[v] = d
    for e in tree[v]:
        if e[0] != p:
            DFSN(e[0], v, d + e[1])
DFSN(N,0,0)

black = 0
for i in range(1,N):
    if depth[i] <= depthN[i]:
        black += 1

if black > N/2:
    print("Fennec")
else:
    print("Snuke")
N = int(input())
A = list(map(int, input.split()))
L = [0 for i in range(N)]

total = 0

for i in range(N):
  r = 0
  for j in range(N):
    if i != j and A[i] == A[j]:
      r += 1
  L[i] = r
  total += r

total = total // 2

for i in L:
  print(total - L[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
#L = [0 for i in range(N)]
dict = {}

for i in A:
  if i in dict:
    dict[i] = dict[i] + 1
  else:
    dict[i] = 1

#print(dict)
total = 0;
for i in dict:
#  print("i:" + str(i) + " " + str(dict[i]))
  total += dict[i]*(dict[i]-1) // 2

#print("T:" + str(total))

for i in A:
  print(total - dict[i] + 1)
a,b = map(int,input())
print(a*b if a<=9 and b<=9 else -1)

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b if a<=9 and b<=9 else -1)
ab = [int(n) for n in input().split()]

S = ab[0]*ab[1]
L = 2*ab[0] + 2*ab[1]

print(S + " " + L)



### FIXED CODE ###

ab = [int(n) for n in input().split()]
 
S = ab[0]*ab[1]
L = 2*ab[0] + 2*ab[1]
 
print(" ".join(map(str,[S,L])))
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

cnt = 0
ans = 0
while cnt < M:
    min_cost = min(A)
    amount = B[A.index(min_cost)]
    if cnt + amount <= M:
        ans += min_cost * amount
        cnt += amount
    else:
        ans += min_cost * (M - cnt)
        break
    A = [e for e in A if e != min_cost]
    B = [e for e in B if e != amount]
    
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

print(ans)
n , k = map(int, input().split())
if k == 2:
    print(n-1)
elif k == n-1:
    print(2)
elif n%2 != 0 k%2 == 0 and (n-k)%(k-1) != 0:
  	print(n//(k-1) + 1)
else:
    print(n//(k-1))

### FIXED CODE ###

n , k = map(int, input().split())
if k == 2:
    print(n-1)
elif k == n-1:
    print(2)
elif (n-k)%(k-1) == 0:
    print((n-k)//(k-1) +1)
else:
    print((n-k)//(k-1) + 2)
b=input()
print(b.translate(str.maketrans('A':'x','C':'y','T':'A','G':'C','x':'C','y':'G')))

### FIXED CODE ###

b=str(input())
print(b.translate(b.maketrans({'A':'T','C':'G','T':'A','G':'C'})))
N, M = map(int, input().split())
a = [-10]
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    for i in range(M):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
a.pop(0)
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            if j < len(a) - 1:
                j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a = []
ans = -1
MOD = 10 ** 9 + 7
if N == 1:
    ans = 1
else:
    if M > 0:
        a += [int(input())]
    for i in range(M - 1):
        a += [int(input())]
        if a[i + 1] - a[i] == 1:
            ans = 0
            break
    a.append([-1])
if not ans in [0, 1]:
    memo = [0] * (N + 1)
    memo[0] = 1
    memo[1] = 1
    try:
        if a[0] == 1:
            a.pop(0)
            memo[1] = 0
    except:
        pass
    j = 0
    for i in range(N - 1):
        if i + 2 == a[j]:
            j += 1
            continue
        memo[i + 2] = memo[i] + memo[i + 1]
        memo[i + 2] = memo[i + 2] % MOD
    else:
        ans = memo[i + 2]
print(ans)
45tokabaguruna

### FIXED CODE ###

x=int(input())
from math import gcd
g=gcd(x,360)
print(360//g)
N, M = map(int(), input().split())
Mylist = []
for i in range(M):
  S = input()
  Mylist.append(S)

ANSlist = sorted(Mylist)
ANS = ''.join(ANSlist)
print(ANS)
  

### FIXED CODE ###

N, M = map(int, input().split())
Mylist = []
for i in range(N):
  S = input()
  Mylist.append(S)
 
ANSlist = sorted(Mylist)
ANS = ''.join(ANSlist)
print(ANS)
x,n = [int(x) for x in input().split()]
if n == 0:
  print(x)
else:
  p = [int(x) for x in input().split()]
  p.sort()
  ans = []
  for i in range(1,101):
    if i in p:
      continue
    b = abs(x - i)
    ans.append((i,b))
  ans = sorted(ans,key = lambda x: x[1])
  print(ans)
  print(ans[0][0])

### FIXED CODE ###

X, N = map(int, input().split())
p = list(map(int, input().split()))
for d in range(X + 1):
  for s in [-1, +1]:
    a = X + s * d
    if p.count(a) == 0:
      print(a)
      exit(0)
N,M = map(int,input().split())
ans = 0
for i in range(M):
  A = int(input())
  N -= M
if N >= 0:
  print(N)
else:
  print("-1")

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
ans = N - sum(A)
if ans >= 0:
  print(ans)
else:
  print("-1")
import sys
input = sys.stdin.readline
S=int(input())
K=len(str(S))
lst= [x for x in list(str(S))]
A=[[0 for v in range(2016)] for j in range(2019)]
A[int(lst[0])][0]+=1
for i in range(1,K):
 c=int(lst[i])
 A[c][i]+=1
 for k in range(2019):
  d=(k*10+c)%2019
  A[d][i]+=A[k][i-1]
print(sum(A[0]))


### FIXED CODE ###

S=input()
T=len(S)
a=0
d=1
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(d))%2019
 b=a%2019
 mod[b]+=1
 d*=10
 d%=2019
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))
k=int(input())
s=input()

mod=10**9+7

import sys
sys.setrecursionlimit(10**15)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

for i in range(k+1):
    ans = (ans+cmb(i+len(s)-1,i,mod)*pow(26,k-i,mod)*pow(25,i,mod)) % mod

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)





### FIXED CODE ###

k=int(input())
s=input()

mod=10**9+7

import sys
sys.setrecursionlimit(10**9)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 2*(10 ** 6)  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

for i in range(k+1):
    ans = (ans+cmb(i+len(s)-1,i,mod)*pow(26,k-i,mod)*pow(25,i,mod)) % mod

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)
s=input()
if s[0]==s[1] or s[0]==s[2] or s[1]==s[2]:
    print(″No″)
else:
    print(″Yes″)

### FIXED CODE ###

s=list(input())
if s[0]==s[1] or s[0]==s[2] or s[1]==s[2]:
    print("No")
else:
    print("Yes")
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

A, B, K = map(int, input().split(" "))

a_divisor = divisor(A)
b_divisor = divisor(B)

print(sorted(list(set(a_divisor) & set(b_divisor)), reverse=True)[1])

### FIXED CODE ###

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

A, B, K = map(int, input().split(" "))

a_divisor = divisor(A)
b_divisor = divisor(B)

print(sorted(list(set(a_divisor) & set(b_divisor)), reverse=True)[K-1])
N = int(input())
S = input()

# print(S.count('ABC'))

cnt = 0
for i in range(N):
    if S[i] == 'A' and S[i + 1] == "B" and S[i + 2] == "C":
        cnt += 1

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

print(S.count('ABC'))
# きりみんちゃんの配信をみてたので期待値は分かる
# 素直にTLEくらったので累積和で加減する
# え これでもだめなの
# あほだった sumしてるし
# 単純にみたら 0.5ずつ増えてるのでそうするか
# 1WA...
# N = 1の場合か？


n, k = map(int, input().split())
arr = list(map(int, input().split()))
table = {}
ans = 0
for i in range(1, 1000 + 1):
    table[i] = (i + 1) * 0.5
if n == 1:
    print(etable[arr[0]])
    exit()
lis = [0 for _ in range(n)]
lis[0] = table[arr[0]]
for i in range(n - 1):
    if i + 1 < k:
        lis[i + 1] = lis[i] + table[arr[i + 1]]
    else:
        lis[i + 1] = lis[i] + table[arr[i + 1]] - table[arr[i - k + 1]]
    ans = max(ans, lis[i + 1])
print(ans)


### FIXED CODE ###

# きりみんちゃんの配信をみてたので期待値は分かる
# 素直にTLEくらったので累積和で加減する
# え これでもだめなの
# あほだった sumしてるし
# 単純にみたら 0.5ずつ増えてるのでそうするか
# 1WA...
# N = 1の場合か？


n, k = map(int, input().split())
arr = list(map(int, input().split()))
table = {}
ans = 0
for i in range(1, 1000 + 1):
    table[i] = (i + 1) * 0.5
if n == 1:
    print(table[arr[0]])
    exit()
lis = [0 for _ in range(n)]
lis[0] = table[arr[0]]
for i in range(n - 1):
    if i + 1 < k:
        lis[i + 1] = lis[i] + table[arr[i + 1]]
    else:
        lis[i + 1] = lis[i] + table[arr[i + 1]] - table[arr[i - k + 1]]
    ans = max(ans, lis[i + 1])
print(ans)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
m = sum(B)
for t in range(N-1):
    if a[t] + 1 == a[t + 1]:
        m += C[a[t] - 1]
print(m)
         

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
m = 0
for i in range(N):
    m += B[A[i] - 1]
for t in range(N-1):
    if A[t] + 1 == A[t + 1]:
        m += C[A[t] - 1]
print(m)
n = int(input())
a = []

for i in range(n):
    a.append(int(input()))

count = 0

while(True):
    odd = False
    for i in range(n):
        if((a[i] % 2) != 0):
            odd = True
    if(odd):
        break
    for i in range(n):
        a[i] /= 2 
        count += 1
print(count)


### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
     #a = [].append(input())
count = 0

while(True):
    odd = False
    for i in range(0,n):
        if a[i]%2==1:
            odd = True
    if(odd):
        break
    for i in range(0,n):
        a[i] /= 2 
    count += 1


print(count)
import math
a, b, c, d=map(int, input().split())
k=math.gcd(c, d)
lcm=c*d//k
x=b//c - a//c
y=b//d - a//d
z=b//lcm - a//lcm
print(b-a+1-(x+y-z))

### FIXED CODE ###

import fractions
a, b, c, d=map(int, input().split())
k=fractions.gcd(c, d)
lcm=c*d//k
x=b//c - (a-1)//c
y=b//d - (a-1)//d
z=b//lcm - (a-1)//lcm
print(b-a+1-(x+y-z))
N = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = s[i] + a[i]
#s[i+1]にはa[0]からa[i]までの総和

nums = [0 for i in range(N+1)]
for i in range(N+1):
    nums[s[i]] += 1

ans = 0
for i in range(N+1):
    ans += nums[i]*(nums[i]-1)/2

print(int(ans))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = s[i] + a[i]
#s[i+1]にはa[0]からa[i]までの総和

dic = {}
for i in range(N+1):
    if dic.get(s[i]) == None:
        dic[s[i]] = 1
    else:
        dic[s[i]] += 1

ans = 0
for k in dic:
    ans += dic[k]*(dic[k]-1)/2

print(int(ans))
line = input()
r = int(line)

pi = 3.1415926535

print('%f %f' % (r*r*pi, 2*r*pi) )

### FIXED CODE ###

line = input()
r = float(line)

import math

print('%f %f' % (r*r*math.pi, 2*r*math.pi) )
k = input()
s = raw_input()

left = 0; right = int(s)
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = 0
    for c in s:
        now = 10*now + int(c)
        if now > mid:
            cnt += 1
            now = int(c)
            if now > mid:
                cnt = 100003
                break
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
E = []
for i in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a-1, b-1))
E.sort()

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

L = 2*N-1
G = [[]] * L
C = [0]*L
*lb, = range(N)
cur = N

s = 0
for c, a, b in E:
    pa = root(a); pb = root(b)
    if pa == pb:
        continue
    s += c
    chds = [lb[pa], lb[pb]]
    if pa < pb:
        p[pb] = pa
        lb[pa] = cur
    else:
        p[pa] = pb
        lb[pb] = cur
    C[cur] = c
    G[cur] = chds
    cur += 1

H = [0]*L
prv = [-1]*L
def dfs(v):
    s = 1; heavy = -1; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(L-1)

SS = []
D = []
LB = [0]*L
I = [0]*L
que = deque([(L-1, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v != -1:
        I[v] = len(S)
        S.append(v)
        LB[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


def query(u, v):
    lu = LB[u]; lv = LB[v]
    dd = D[lv] - D[lu]
    if dd < 0:
        lu, lv = lv, lu
        v, u = u, v
        dd = -dd

    for _ in range(dd):
        v = prv[SS[lv][0]]
        lv = LB[v]

    while lu != lv:
        u = prv[SS[lu][0]]
        lu = LB[u]

        v = prv[SS[lv][0]]
        lv = LB[v]

    return u if I[u] < I[v] else v


def gen():
    Q = int(input())
    for i in range(Q):
        u, v = map(int, input().split())
        w = query(u-1, v-1)
        yield "%d\n" % (s - C[w])
ans = list(gen())
sys.stdout.writelines(ans)
k, n = map(int, input().split())

An = list(map(int, input().split()))

node = [An[i+1] - An[i]  for i in range(len(An) - 1)]

node = node[:] + [k - An[n-1] + An[0]]

print(k - max(node))

### FIXED CODE ###

S = input()
if (S[2] == S[3]) and (S[4] == S[5]):
    print('Yes')
else:
    print('No')
from collections import defaultdict

N,M = map(int,input().split())
AB =defaultdict(list)
total = 0
for _ in range(N):
    A,B = map(int,input().split())
    AB[A].append(B)
while M > 0:
    minAB = AB[min(AB)]
    if minAB[0] <= M:
        #print('あと{}'.format(M))
        M -= minAB[0]
        total += min(AB) * minAB[0]
        del AB[min(AB)]
    else:
        #print('残り{}'.format(M))
        total += min(AB) * M
        M -= M
print(total)

### FIXED CODE ###

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort()
ans = 0
while M > 0:
    ab = AB[0]
    if ab[1] <= M:
        M-= ab[1]
        ans += ab[0] * ab[1]
        AB.pop(0)
    else:
        ans += ab[0] * M
        M -= M
print(ans)
S = input()
inputInInt = int(S)
sum = 0
for i in range(S):
    sum += S[i]

if inputInInt % sum is 0:
    print('YES')
else:
    print('No')


### FIXED CODE ###

S = input()
inputInInt = int(S)
sum = 0
for i, v in enumerate(S):
    sum += int(v)

if inputInInt % sum is 0:
    print('Yes')
else:
    print('No')
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '));

board = []
flags = [ True for x in range(W)]
for i in range(H):
    line = list(input())
    if ( '#' in line ):
        board.append(line)
        flags = [ f and s == '.' for s,f in zip(line, flags) ]

j = 0
for i, flag in enumerate(flags):
    if flag:
        for b in board:
            b.pop(i-j)
            j += 1
for b in board:
    print(''.join(b))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
H, W = map(int, input().split(' '));

board = []
flags = [ True for x in range(W)]
for i in range(H):
    line = list(input())
    if ( '#' in line ):
        board.append(line)
        flags = [ f and s == '.' for s,f in zip(line, flags) ]

j = 0
for b in board:
    for l,flag in zip(b,flags):
        if not flag:
            sys.stdout.write(l)
    print()
s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
    
        elif s[i-1] =='P' :
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1 or s[i+1] == 'P'):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)
 
#cnt = s.count('PD')
#cnt += s.count('D')
 
print(s)

### FIXED CODE ###

s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and len(s) == 1:
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
        elif s[i-1] =='P':
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1):
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i <len(s)-1 and(s[i+1] == 'P' or s[i+1] == '?')):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)


print(s)
N,Y = map(int, input().split())
for i in range(N+1):
  for j in range(N+1-i):
    k = N-i-j
      if Y == 10000*i + 5000*j + 1000*k:
        print(i j k)
        sys.exit()
print(-1 -1 -1)

### FIXED CODE ###

S = list(input())
S[3] = "8"
print("".join(S))
r=int(input())
if r<1200:
  print('ABC')
elif　1200<=r<2800:
  print('ARC')
else:
  print('AGC')

### FIXED CODE ###

r=int(input())
if r<1200:
    print('ABC')
elif r<2800:
    print('ARC')
else:
    print('AGC')
import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * b
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i, n-1] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

print(ans)



### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * (b - max(0, pos-n))
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

print(ans)