Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N=int(input())
x=input()

def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

if GroundOnes>1:
    for j in range(N):
      TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
      TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
else:
    for j in range(N):
      TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-TwoPowerCaseOne[i]
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+TwoPowerCaseZero[i]
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))

### FIXED CODE ###

N=int(input())
x=input()
def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

# if GroundOnes>1:
#     for j in range(N):
#       TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
# else:
#     for j in range(N):
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 1001001001

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
# print(S)

ans = INF
for b in range(1<<(H-1)):
    g = 0
    idx = [0]*H
    for i in range(H-1):
        if b>>i&1:
            g += 1
        idx[i+1] = g
    g += 1
    cnt = [[0]*W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            cnt[idx[i]][j] += S[i][j]
    num = g-1
    now = [0]*g

    def add(j):
        global now
        for i in range(g):
            now[i] += cnt[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if add(j)==False:
            num += 1
            now = [0]*g
            if add(j)==False:
                num = INF
                break
    ans = min(ans, num)

print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 1001001001

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
# print(S)

ans = INF
for b in range(1<<(H-1)):
    g = 0
    idx = [0]*H
    for i in range(H-1):
        if b>>i&1:
            g += 1
        idx[i+1] = g
    g += 1
    cnt = [[0]*W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            cnt[idx[i]][j] += S[i][j]
    num = g-1
    now = [0]*g

    def add(j):
        global now
        for i in range(g):
            now[i] += cnt[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if add(j)==False:
            num += 1
            now = [0]*g
            if add(j)==False:
                num = INF
                break
    ans = min(ans, num)

print(ans)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)

@lru_cache(maxsize=None)
def dp(k, A, turn):
    for i in A:
        if i > k:
            break
        if dp(k - i, A, not turn) == turn:
            return turn
    return not turn
    

def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    print('First' if dp(K, A, True) else 'Second')


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    c = [0] * (K + 1)
    def dp(k, A, c, turn):
        if c[k] != 0:
            return c[k] * turn
        for i in A:
            if i > k:
                break
            if dp(k - i, A, c, -turn) == turn:
                c[k] = 1
                return turn
        c[k] = -1
        return -turn
    
    print('First' if dp(K, A, c, 1) == 1 else 'Second')


main()
### BUGGY CODE ###

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

res = 0
bits = [[0]*2 for _ in range(60)]
for a in al:
    for i in range(60):
        bits[i][int(bin(a >> i)[-1])] += 1

res = 0

for i in range(60):
    res += bits[i][0] * bits[i][1]  * (2 ** i)

print(res % (10 ** 9 + 7))


### FIXED CODE ###


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

res = 0
bits = [0]*60
for a in al:
    i = 0
    b = a
    while b:
        bits[i] += b&1
        b = b >> 1
        i += 1

res = 0

for j in range(60):
    res += bits[j] * (n - bits[j])  * (2 ** j)

print(res % (10 ** 9 + 7))
### BUGGY CODE ###

import fractions
from itertools import combinations
def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
def compromise(x1, x2):
    f = fractions.gcd(x1, x2)
    return f == 1

a, b = map(int, input().split())
cfs = cf(a, b)
club = []
for i in range(len(cfs)):
    if i == 0:
        club.append(cfs[i])
    else:
        flag = True
        for c in club:
            if not compromise(cfs[i], c):
                flag = False
        if flag:
            club.append(cfs[i])
print(len(club))

### 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
a, b = map(int, input().split())
apri = set(prime_factorize(a))
bpri = set(prime_factorize(b))
print(len(apri & bpri)+1)
### BUGGY CODE ###

def main():
  import sys
  sys.setrecursionlimit(int(1e+6))
  N, Q = map(int, input().split())
  ab = [list(map(int, input().split())) for _ in range(N-1)]
  px = [list(map(int, input().split())) for _ in range(Q)]

  branch = [[] for _ in range(N)]
  for i in range(N-1):
      branch[ab[i][0]-1].append(ab[i][1]-1)
      branch[ab[i][1]-1].append(ab[i][0]-1)

  counters = [0 for _ in range(N)]
  for i in range(Q):
      counters[px[i][0]-1] += px[i][1]

  results = [0 for _ in range(N)]

  def repeat(node, counter, pre_node):
      counter += counters[node]
      for candidate in branch[node]:
          if candidate == pre_node:
              continue
          else:
              repeat(candidate, counter, node)
      results[node] = counter
      return

  repeat(0, 0, 0)

  print((" ").join([str(i) for i in results]))
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

branch = [[] for _ in range(N)]
for i in range(N-1):
    branch[ab[i][0]-1].append(ab[i][1]-1)
    branch[ab[i][1]-1].append(ab[i][0]-1)

counters = [0 for _ in range(N)]
for i in range(Q):
    counters[px[i][0]-1] += px[i][1]
results = [0 for _ in range(N)]

seen = [False for _ in range(N)]
from collections import deque
seen[0] = True
todo = deque([0])
results[0] = counters[0]

while len(todo)>0:
    checking = todo.pop()
    candidates = branch[checking]
    for candidate in candidates:
        if seen[candidate] == False:
            todo.append(candidate)
            seen[candidate] = True
            results[candidate] = results[checking]+counters[candidate]


print((" ").join([str(i) for i in results]))
### BUGGY CODE ###

import bisect

N = int(input())
A = [int(input()) for i in range(N)]

colors = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.insert(0, A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))


### FIXED CODE ###

from collections import deque
import bisect

N = int(input())
A = [int(input()) for i in range(N)]

colors = deque()
for i in range(N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.appendleft(A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))
### BUGGY CODE ###

N,K=map(int,input().split())
h=[int(x) for x in input().split()]
h.extend([0]*(N+K))
dp=[float('inf')]*(len(h))
dp[0] = 0
for i in range(N):
  for j in range(1,K+1):
    dp[i+j]=min(dp[i+j],dp[i]+abs(h[i] - h[i+j]))
     
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=[int(x) for x in input().split()]

dp=[float('inf')]*N
dp[0] = 0

for i, hi in enumerate(h):
  if i > 0:
    x = max(0,i-K)
    dp[i]=min([dpj + abs(hi-hj) for dpj, hj in zip(dp[x:i], h[x:i])])
     
print(dp[N-1])
### BUGGY CODE ###

def main(): 
    n = int(input())
    h = list(map(int, input().split()))

    max_i = 0
    
    for i in range(n):
        cnt = 0
        for j in range(i+1, n):
            if h[j-1] >= h[j]:
                cnt += 1
            else:
                break
        max_i = max(max_i, cnt)
        if max_i >= n - i - 1:
            break
    print(max_i)

if __name__ == "__main__":
    main() 

### FIXED CODE ###

def main(): 
    n = int(input())
    h = list(map(int, input().split()))

    max_i = 0
    i = 0 
    while i < n:
        cnt = 0
        for j in range(i+1, n):
            if h[j-1] >= h[j]:
                cnt += 1
            else:
                i = j
                break
                
        max_i = max(max_i, cnt)
        if max_i >= n - i - 1:
            break
    print(max_i)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input().split()
    if len(b)>1:c=int(b[1])
    b=b[0]
    if b[0]=='i':a.appendleft(c)
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
    else:
        try:a.remove(c)
        except:pass
print(*a)

### FIXED CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input()
    if b[0]=='i':a.appendleft(b[7:])
    elif b[6]==' ':
        try:a.remove(b[7:])
        except:pass
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
print(*a)
### BUGGY CODE ###

s=list(input())
q=int(input())
info=[]
for i in range(q):
    info.append(list(input().split()))
for i in range(q):
    if info[i][0]=="1":
        s.reverse()
    else:
        if info[i][1]=="2":
            s.append(info[i][2])
        else:
            s.insert(0,info[i][2])
    #print(s)
print("".join(s))

### FIXED CODE ###

from collections import deque
ss=deque()
s=list(input())
l=len(s)
for i in range(l):
    ss.append(s[i])
q=int(input())
info=[]
rev=[] #i回までに何回反転があるか
num=0
for i in range(q):
    info.append(list(input().split()))
moji=0 #文字の追加数
for i in range(q):
    if info[i][0]=="1":
        num+=1
    else:
        if info[i][1]=="2":
            rev.append([info[i][2],2,num]) #末尾
        else:
            rev.append([info[i][2],1,num])
        moji+=1
if num%2==1:
    ss.reverse()
#print(rev)
#print(num)
for i in range(moji):
    now=rev[i][1]
    if (num-rev[i][2])%2==1: #これが奇数だと２なら先頭になる
        #print("change")
        if rev[i][1]==2:
            rev[i][1]=1
        else:
            rev[i][1]=2
    if rev[i][1]==2:
        ss.append(rev[i][0])
    else:
        ss.appendleft(rev[i][0])
print("".join(ss))
#print(rev)
### BUGGY CODE ###

def moddiv(a, b, mod):
    inverted_b = pow(b, mod-2, mod)
    return (a*inverted_b) % mod
def main():
    mod = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    for a in A:
        for i in reversed(range(a, S + 1)):
            dp[i] = (dp[i] + moddiv(dp[i - a], 2, mod)) % mod
    return dp[S]

print(main())


### FIXED CODE ###

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

def solve(N, S, A):
    mod = 998244353
    dp = [0] * (S + 1)
    dp[0] = pow(2, N, mod)
    div2 = pow(2, mod - 2, mod)
    m = 0
    for a in A:
        m += a
        for i in reversed(range(a, min(S, m) + 1)):
            dp[i] = (dp[i] + dp[i - a] * div2) % mod
    return dp[S]

print(main())
### BUGGY CODE ###

import collections
N = int(input())
S = input()
ans = 0
table = collections.defaultdict(list)
for i in range(1, N//2 + 1):
    for j in range(N-i+1):
        table[S[j:j+i]].append(j)

ans = 0
for x in table:
    n = len(x)
    if n <= ans:
        continue
    if table[x][-1] - table[x][0] >= n:
        ans = max(ans, n)

print(ans)


### FIXED CODE ###

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

s=[[0]*N for i in range(N)]
k=0
for k in range(N):
  s[k]= [0]*k + z_algo(S[k:])

ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i > j:
      ans = max(ans,j - i)
    else:
      ans=max(s[i][j],ans)
    
print(ans)
### BUGGY CODE ###

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

def main(N, A_list):
    num = len(A_list)
    tmp = []
    for i in range(0, num, 1):
        for j in range(i+1, num, 1):
            tmp.append(A_list[i] * A_list[j])

    val = sum(tmp) % ((10 ** 9) + 7)
    print(val)


N = int(input())
A_list = list(map(int, input().split()))
main(N, A_list)

### FIXED CODE ###

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

def main(N, A_list):
    total_list = []
    total = 0
    for i in range(len(A_list)):
        total += A_list[i]
        total_list.append(total)

    num = 0
    for i in range(len(A_list)-1):
        num += A_list[i] * (total_list[len(A_list)-1]-total_list[i])

    val = num % ((10 ** 9) + 7)
    print(val)


N = int(input())
A_list = list(map(int, input().split()))
main(N, A_list)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
SC=tuple(SC)

#N=300
#SC=(N-2,1,1,0)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[0]<0 or SC[1]<0 or SC[2]<0:
        return 0

    k=sum(SC)

    if k==0:
        return 0

    DAYSDICT[SC]=(days((SC[0]-1,SC[1],SC[2]))*SC[0]+days((SC[0]+1,SC[1]-1,SC[2]))*SC[1]+days((SC[0],SC[1]+1,SC[2]-1))*SC[2]+N)/k
    return DAYSDICT[SC]

print(days(SC))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
one,two,three=SC

DAYSDICT=[[[0.0]*301 for j in range(301)] for k in range(301)]
DAYSDICT[0][0][0]=0
def days(one,two,three):
    ANS=N
    if one>0:
        ANS+=DAYSDICT[one-1][two][three]*one
    if two>0:
        ANS+=DAYSDICT[one+1][two-1][three]*two
    if three>0:
        ANS+=DAYSDICT[one][two+1][three-1]*three
        
    DAYSDICT[one][two][three]=ANS/(one+two+three)


for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(one+two+three+1-j-k):
            if i==j==k==0:
                continue
            days(i,j,k)

print(DAYSDICT[one][two][three])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)

### FIXED CODE ###

# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if a[i]==j+1 and a[j]==i+1:
            cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(len(a)):
    if a[a[i]-1]==i+1:
            cnt+=1
print(cnt//2)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
res = 0
a.sort()

for i in range(N):
    X = a.count(i+1)
    if a[i] > N:
        res += 1
        
    elif X < i+1:
        res += X
        i = i  + X
        
    else:
        res += X - (i+1)
        i = i  + X
        
print(res)

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
L = list(set(a))
res = 0
d = Counter()
d.update(a)
for i in L:
    X = d[i]
    if X < i:
        res += X
    
    else:
        res += X - i

print(res)
### BUGGY CODE ###

def main():
    def solve(strings_max, rows_max, mapa):
        summa = maxs + maxr - 1
        if summa == h + w - 1:
            return summa
        for h_item in strings_max:
            for w_item in rows_max:
                if w_item not in mapa.get(h_item, []):
                    return summa + 1
        return summa


    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    maxs = max(strings)
    maxr = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == maxs:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == maxr:
            rows_max.append(i)
    
    ans = solve(strings_max, rows_max, mapa)
    print(ans)

main()


### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    max_s = max(strings)
    max_r = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == max_s:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == max_r:
            rows_max.append(i)
    
    forbidden_positions = set(mapa[strings_max[0]])
    for item in strings_max[1:]:
        forbidden_positions.intersection_update(set(mapa[item]))

    answer_set = set(rows_max).difference(forbidden_positions)
    if answer_set:
        print(max_s + max_r)
    else:
        print(max_s + max_r - 1)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
As = sorted(As)
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  t = len([x for x in As if x<C])
  if t > 0:
    if t > B:
      As = As[B:]
      As.extend([C]*B)
    else:
      As = As[t:]
      As.extend([C]*t)
    As=sorted(As)
print(sum(As))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
d2 = sorted([x for x in d.keys()],reverse=True)
for m in d2:
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
print(res)
### BUGGY CODE ###

p = input().split()

k = int(p[0])
s = int(p[1])

x = -1
y = -1
z = -1
answer = 0

for number in range(k+1):
    x += 1
    y = -1
    z = -1
    for num in range(k+1):
        y += 1
        z = -1
        for n in range(k+1):
            z += 1
            if x + y + z == s:
                answer += 1

print(answer)     

### FIXED CODE ###

p = input().split()

k = int(p[0])
s = int(p[1])

x = -1
y = -1
z = 0
answer = 0

for num in range(k+1):
    x += 1
    y = -1
    for n in range(k+1):
        y += 1
        z = s - x - y
        if 0 <= z and z <= k:
            answer += 1
 



print(answer)
### BUGGY CODE ###

t = input()
ans = ''

if t[0] == '?':
    if len(t) > 1:
        ans += 'P'
    else:
        ans += 'D'
else:
    ans += t[0]

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

print(ans)

### FIXED CODE ###

t = input()
ans = ''

t = t.replace('?', 'D')
print(t)
### BUGGY CODE ###

s = input()
t = input()
dp = [[0 for _ in range(len(s)+1)] for i in range(len(t)+1)]
ans = ""
res = []
for i in range(len(t)+1):
    dp[i][0] = 0
for j in range(len(s)+1):
    dp[0][j] = 0
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            res.append([i,j])
            
            
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
i,j = len(t),len(s)
while i > 0 and j > 0:
    if [i,j] in res:
        ans += s[j-1]
        i,j = i-1,j-1
        continue
        
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
    
print(ans[::-1])

### FIXED CODE ###

import numpy as np
 
t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')
 
ls = len(s)
lt = len(t)
 
eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]
 
# solve
for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)
 
# print([list(line) for line in dp])
 
# restore
l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
 
print(res[::-1])