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

h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
ans = 0
while True:
    for i in range(h):
        for j in range(w):
            if al[i][j] == ".":
                break
        else:
            continue
        break
    else:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
    job = job2
            



### FIXED CODE ###

h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
c = 0
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
            c += 1
ans = 0
while True:
    if c == h*w:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
                    c += 1
    job = job2
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

Q = deque()
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            A[h][w]="."
            Q.append((0,h,w))
ans = 0
while Q:
    cnt,h,w = Q.popleft()
    if min(h,w)<0 or h>=H or w>=W:continue
    if A[h][w]=="#":continue
    A[h][w] = "#"
    ans = max(cnt,ans)
    for i in [-1,1]:
        Q.append((cnt+1,h+i,w))
        Q.append((cnt+1,h,w+i))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

n = int(input())
before = [0, 0]
for i in range(n):
    t, a = map(int, input().split())
    if t >= before[0] and a >= before[1]:
        before = [t, a]
    else:
        i=2
        _t=t
        _a=a
        while _t<before[0] or _a<before[1]:
            _t=t*i
            _a=a*i
            i+=1
        before=[_t,_a]
print(sum(before))

### FIXED CODE ###

n = int(input())
before = [0, 0]
for i in range(n):
    t, a = map(int, input().split())
    if t >= before[0] and a >= before[1]:
        before = [t, a]
    else:
        mul = max((before[0]-1)//t+1, (before[1]-1)//a+1)
        before = [t*mul, a*mul]

print(sum(before))
### BUGGY CODE ###

mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

#def combi(n,k):
#  return ((fac[n]*(expo_fac[k])%mod)*expo_fac[n-k]%mod)

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

expo_fac = [expo(fac[i]) for i in range(n+1)]

ans = 0
for i in range(min(n,k+1)):
  ans = (ans + ((fac[n]*(expo_fac[i])%mod)*expo_fac[n-i]%mod)*((fac[n-1]*(expo_fac[i])%mod)*expo_fac[n-i-1]%mod)%mod)%mod
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

ans = 1
for i in range(1,min(n,k+1)):
    ans += combi(n,i)*combi(n-1,i)%mod
    ans %= mod
print(ans)
### BUGGY CODE ###

def main():
    N, T = map(int, input().split())
    foods = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i, food in enumerate(foods):
        now_foods = foods[:i] + foods[i+1:]
        dp = [[0] * T for _ in range(N)]
        for j, n_food in enumerate(now_foods):
            n_a, n_b = n_food
            for k in range(T):
                if k < n_a:
                    dp[j+1][k] = dp[j][k]
                else:
                    dp[j+1][k] = max(dp[j][k], dp[j][k-n_a]+n_b)
        #print(dp[j+1])
        ans = max(ans, dp[-1][-1]+food[1])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from operator import itemgetter


def main():
    input = sys.stdin.readline
    N, T = map(int, input().strip().split())
    foods = sorted([list(map(int, input().strip().split())) for _ in range(N)], key=itemgetter(0))

    ans = 0
    dp = [[0] * (T+1) for _ in range(N+1)]
    for j, food in enumerate(foods):
        n_a, n_b = food
        for k in range(T+1):
            if k == T:
                dp[j+1][k] = max(dp[j][k], dp[j][k-1]+n_b)
            elif k < n_a:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-n_a]+n_b)
        #print(dp[j+1])
    ans = dp[-1][-1]
    print(ans)

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

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
    print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

S = input()
a = [0]
b = [0]*2019
c = 0
d = 0
for n in range(len(S)):
    c += 10**n*int(S[-n-1])
    a.append(c%2019)
for n in range(len(S)+1):
    b[a[n]] += 1
for n in range(2019):
    d += int(b[n]*(b[n]-1)/2)
print(d)

### FIXED CODE ###

S = input()
l = len(S)
a = [0]
b = [0]*2019
c = [1]
d = 0
e = 0
for n in range(l-1):
    c.append(c[n]*10%2019)
for n in range(l):
    d += int(S[-n-1])*c[n]
    a.append(d%2019)
for n in range(l+1):
    b[a[n]] += 1
for n in range(2019):
    e += int(b[n]*(b[n]-1)/2)
print(e)
### BUGGY CODE ###

a, v = map(int,input().split())
b, w = map(int,input().split())
t = int(input())
for i in range(t):
    a = a + v
    b = b + w
if a >= b :
    print("YES")
else:
    print("NO")

### FIXED CODE ###


a, v = map(int,input().split())
b, w = map(int,input().split())
t = int(input())

if a > b:
    v = -v
    if w > 0:
        w = -w
if a < b and  w < 0:
    w = -w



A = t * v + a
B = t * w + b

if A > B:
    if  a < b:
        print("YES")
    else:
        print("NO")
elif A == B:
    print("YES")
elif A < B :
    if a < b:
        print("NO")
    else:
        print("YES")
### BUGGY CODE ###

s = input()
k = int(input())
x = []
n = len(s)
for i in range(n):
    for j in range(n-i):
        x.append(s[j:j+i+1])
y = list(set(x))
y.sort()
print(y[k-1])


### FIXED CODE ###

s = input()
k = int(input())
x = []
n = len(s)
for i in range(k):
    for j in range(n-i):
        t = s[j:j+i+1]
        if not t in x:
            x.append(t)
x.sort()
print(x[k-1])
### BUGGY CODE ###

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = [None] * n
queue[0] = 1
idx = 1

ans = [None] * n 

for i in queue:
  next_room = pathes[i] - set(queue)
  for j in next_room:
    ans[j-1] = str(i)
    queue[idx] = j
    idx += 1

ans[0] = "Yes"

print("\n".join(ans))


### FIXED CODE ###

from collections import deque

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

pathes = {i: set() for i in range(1, n + 1)}
for _ in range(m):
  ai, bi = map(int, input().split()) 
  pathes[ai].add(bi)
  pathes[bi].add(ai)

queue = deque()
queue.append(1)

ans = [None] * n 

for _ in range(n):
  if len(queue) == 0:
    break;
  i = queue.popleft()
  next_room = pathes[i]
  for j in next_room:
    if ans[j-1] == None:
      ans[j-1] = str(i)
      queue.append(j)

ans[0] = "Yes"

print("\n".join(ans))
### BUGGY CODE ###

def main():
    N,K=map(int,input().split())
    L=[int(x) for x in input().split()]
    LL=[L[i]*L[i+j] for i in range(0,N) for j in range(1,N-i)]
    print(sorted(LL)[K-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)
### BUGGY CODE ###

h,w=map(int,input().split())
cnt=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if (i+j)%2==0:
            cnt+=1
print(cnt)


### FIXED CODE ###

h,w=map(int,input().split())
if h==1 or w==1:
    print(1)
    exit()
if h%2+w%2==0:
    print((h//2)*w)
elif h%2==1 and w%2==0:
    print((w//2)*h)
elif w%2==1 and h%2==0:
    print((h//2)*w)
else:
    print((h//2+1)*(w-w//2)+(h//2)*(w//2))
### BUGGY CODE ###

import sys,bisect
input = sys.stdin.readline
 
x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = tuple(map(int,input().split()))
 
ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()
 
ok = -1
ng = 10**11
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid
 
res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
### BUGGY CODE ###

from itertools import combinations

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# bit DP...?
dp = [[0] * (2 ** n) for i in range(n + 1)]
dp[0][0] = 1

bitcal = sorted([pow(2, i) for i in range(n)], reverse=True)
bitlist = [[i] for i in range(n)]  # 1が少ない順に作りたい...
for i in range(1,n):
    bitlist = bitlist + list(combinations(range(n), i + 1))

for bit in bitlist:
    i = len(bit)
    j = sum(bitcal[k] for k in bit)
    for num in bit:
        dp[i][j] += dp[i - 1][j - 2 ** (n - num - 1)] * a[i - 1][num]
    dp[i][j] %= mod

print(dp[n][2 ** n - 1])


### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

def is_ok(x, A, F):
    trainings = 0
    for i in range(N):
        t = A[i] - x // F[i]
        if t > 0:
            trainings += t
    return trainings <= K


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

A.sort()
F.sort(reverse=True)

ng = -1
ok = A[-1] * F[0]
while ok - ng > 1:
    m = ng + (ok - ng) // 2
    if is_ok(m, A, F):
        ok = m
    else:
        ng = m
print(ok)


### FIXED CODE ###

def f(x, A, F):
    result = 0
    for i in range(N):
        t = x // F[i]
        if t < A[i]:
            result += A[i] - t
    return result


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

A.sort()
F.sort(reverse=True)

lo = 0
hi = A[-1] * F[0]
while lo < hi:
    mid = (lo+hi)//2
    if K - f(mid, A, F) < 0:
        lo = mid+1
    else:
        hi = mid
print(lo)
### BUGGY CODE ###

import numpy as np

N, M, X = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(N)]

data_a = np.sum(data, axis=0)
#print(data_all - data[1])
data_all_zero = []
data_all = []
data_nolma = []
data_nolma.append(0)
for i in range(M + 1):
    data_all_zero.append(data_a[i])

data_all.append(data_all_zero)
#print("data_all:", data_all)

for i in range(M):
    data_nolma.append(X)

#print("data_nol:", data_nolma)





for i in range(N):
    for j in range(N):
        for k in range(len(data_all)):
            #print("data[j]:", data[j])
            #print("len:", len(data_all))
            data_tmp = [x - y for (x,y) in zip(data_all[k], data[j])]
            #print("data_tmp:", data_tmp)
            data_tmp_nol = [x - y for (x,y) in zip(data_tmp, data_nolma)]
            #print("data_tmp_nol:", data_tmp_nol)
            if(min(data_tmp_nol) >= 0):
                data_all.append(data_tmp)


#print(data_all)
data_all.sort()

flag = 0
for i in range(1, len(data_all[0])):
    if(data_all[0][i] < X):
        print(-1)
        flag = 1
        break
if(flag == 0):
    print(data_all[0][0])

### FIXED CODE ###

import numpy as np

N, M, X = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

data_all = []
c_min = INF

for i in range(2**N):
    data_tmp = [0]*M
    c = 0
    for j in range(N):
        if((i>>j) & 1):
            for k in range(M):
                data_tmp[k] += data[j][k+1]
            c += data[j][0]
    if(min(data_tmp) >= X):
        c_min = min(c, c_min)

if(c_min == INF):
    print(-1)
else:
    print(c_min)
### BUGGY CODE ###

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

l=[]
n=A.pop()
n2=A.pop()
sum=n
comfort={n2:[[n,n2],[n2,n]]}

while A:
  max=sorted(comfort.keys())[-1]
  if comfort.get(max)==None:print(0)
  n=comfort[max].pop()
  if comfort[max]==[]:del comfort[max]
  sum+=max
  n2=A.pop()
  if comfort.get(min(n[0],n2))==None:comfort[min(n[0],n2)]=[]
  if comfort.get(min(n[1],n2))==None:comfort[min(n[1],n2)]=[]
  comfort[min(n[0],n2)].append([n[0],n2])
  comfort[min(n[1],n2)].append([n[1],n2])
print(sum)

### FIXED CODE ###

input()
A=list(map(int,input().split()))
A.sort(reverse=True)
B=[]
ans=0
for i in A:
  if len(B)>=1:
    ans+=B[len(B)//2]
  B.append(i)
print(ans)
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    A = list([0])
    for j in range(n):
        A.append(a[j])
    A.append(0)
    
    sum = 0
    for i in range(n):
        root = list(A[:])
        del root[i+1]
        for j in range(1, n+1):
            sum += abs(root[j]-root[j-1])
        print(sum)
        sum = 0


### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    A = list([0])
    A.extend(a)
    A.append(0)

    sum = 0
    for i in range(1, n+2):
        sum += abs(A[i]-A[i-1])
    for i in range(1, n+1):
        print(sum-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

if n > k:
    for i in range(k):
        h.remove(max(h))
    print(sum(h))
else:
    print(0)

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
h.sort(reverse=True)

if n > k:
    del h[:k]
    print(sum(h))
else:
    print(0)
### BUGGY CODE ###

s=list(input())
answer = 0
for i in range(len(s)):
    if s[i] == '?':
        s[i] = 'D'
for i in range(len(s)):
    if s[i] == 'P':
        if i < len(s) - 1 and s[i + 1] == 'D':
            answer += 1
    else:
        answer += 1
ans = ""
for i in range(len(s)):
    ans += s[i]
print(ans)
    


### FIXED CODE ###

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

m,n,x=[int(i) for i in input().split()]
a=set(range(m,m+x))
b=set(range(n-x+1,n+1))
c=set(range(m,n+1))
for i in sorted(list((a|b)&c)):
  print(i)

### FIXED CODE ###

m,n,x=[int(i) for i in input().split()]
a=set([i for i in range(m,m+x) if i<=n])
b=set([i for i in range(n-x+1,n+1) if i>=m])
for i in sorted(list(a|b)):
  print(i)
### BUGGY CODE ###

#!/usr/bin/env python3
 
# 以下を記述しないとTLEになる, 何故？
from collections import Counter
import itertools
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

l = input().split()
N = int(l[0])
M = int(l[1])

A = []
for i in range(M):
    l = input().split()
    A.append(int(l[0]))

mod = 1000000007

# print(N, M, A)

DP = [0]*(N+2)
DP[0] = 1
for i in range(N):
    if i in A:
        continue
    DP[i + 1] = (DP[i] + DP[i + 1]) % mod
    DP[i + 2] = (DP[i] + DP[i + 2]) % mod
print(DP[N])


### FIXED CODE ###

N, M = map(int, input().split())
DP = [0]*(N+2)
DP[0] = 1
A = []
for i in range(M):
    a = int(input())
    DP[a] = -1

mod = 1000000007

# print(N, M, A)

for i in range(N):
    if DP[i] == -1:
        continue
    if DP[i + 1] != -1:
        DP[i + 1] = (DP[i] + DP[i + 1]) % mod
    if DP[i + 2] != -1:
        DP[i + 2] = (DP[i] + DP[i + 2]) % mod
print(DP[N])
### BUGGY CODE ###

num = int(input())
a_i = list(map(int, input().split()))
ans = 1
for x in a_i:
    ans *= x
if ans > 10 ** 18: print(-1)
else: print(ans)

### FIXED CODE ###

num = int(input())
a_i = list(map(int, input().split()))
ans = 1
if a_i.count(0) > 0: print(0)
else:
    for x in a_i:
        ans *= x
        if ans > 10 ** 18: 
            ans = -1
            break
    print(ans)