Harryxun/stf_run huggingface dataset:
s = input()
t = input()

ans = "UNRESTORABLE"

ls = []

for i in range(len(t)):
    for j in range(i, len(s)-len(t)+i+1):
        if s[j] == t[i]:
            for k in range(len(t)):
                if t[i+k] != s[j+k] and s[j+k] != "?":
                    break
                if k == len(t)-1:
                    tmps = s[:j-i] + t + s[j-i+len(t):]
                    for p in range(len(s)):
                        if tmps[p] == "?":
                            tmps = tmps[:p] + "a" + tmps[p+1:]
                    ls.append(tmps)

ls.sort()
if len(ls) != 0:
    ans = ls[0]

print(ans)


### FIXED CODE ###

s = input()
t = input()

ans = "UNRESTORABLE"

ls = []

for i in range(len(t)):
    for j in range(i, len(s)-len(t)+i+1):
        if s[j] == t[i]:
            for k in range(len(t)):
                if t[k] != s[j+k-i] and s[j+k-i] != "?":
                    break
                if k == len(t)-1:
                    tmps = s[:j-i] + t + s[j-i+len(t):]
                    for p in range(len(s)):
                        if tmps[p] == "?":
                            tmps = tmps[:p] + "a" + tmps[p+1:]
                    ls.append(tmps)

for i in range(len(s)-len(t)+1):
    if s[i] == "?":
        if s[i:i+len(t)] == "?"*len(t):
            tmps = s[:i] + t + s[i+len(t):]
            for p in range(len(s)):
                if tmps[p] == "?":
                    tmps = tmps[:p] + "a" + tmps[p+1:]
            ls.append(tmps)

ls.sort()
if len(ls) != 0:
    ans = ls[0]

print(ans)
N = int(input())
h = list(map(int, input().split()))

def chmin(a,b):
    if a > b:
        return b
    else:
        return a

dp[0] = 0

for i in range(1,N):
    dp[i] = chmin(dp[i], dp[i-i] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
dp = [0,abs(a[0]-a[1])]
for i in range(2,N):
    dp.append(min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2])))
print(dp[N-1])
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
print(sum[1:2*n+2:2])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
print(sum(a[1:2*n:2]))
def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))
    clist = list(map(int, input().split()))

    return n, alist, blist, clist


def submit():
    n, alist, blist, clist = read_input()

    alist.sort(reverse=True)
    blist.sort(reverse=True)
    clist.sort(reverse=True)

    b_a_n = [0] * n
    i = j = 0

    while j < n:
        while i < n and alist[i] >= blist[j]:
            i += 1
        b_a_n[j] = n - i
        j += 1

    b_a_sum = b_a_n.copy()
    for i in range(2, n + 1):
        b_a_sum[n - i] = b_a_sum[n - i + 1] + b_a_n[n - i]

    count = 0
    i = j = 0
    while i < n:
        while blist[j] >= clist[i]:
            j += 1
            if j == n:
                print(count)
                return
        count += b_a_sum[j]
        i += 1

    print(count)



if __name__ == '__main__':
    submit()

### FIXED CODE ###


def read_input():
    n = int(input())
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))
    clist = list(map(int, input().split()))

    return n, alist, blist, clist


def submit():
    n, alist, blist, clist = read_input()

    alist.sort(reverse=True)
    blist.sort(reverse=True)
    clist.sort(reverse=True)

    b_a_n = [0] * n
    i = j = 0

    while j < n:
        while i < n and alist[i] >= blist[j]:
            i += 1
        b_a_n[j] = n - i
        j += 1

    b_a_sum = b_a_n.copy()
    for i in range(2, n + 1):
        b_a_sum[n - i] = b_a_sum[n - i + 1] + b_a_n[n - i]

    count = 0
    i = j = 0
    while i < n:
        while blist[j] >= clist[i]:
            j += 1
            if j == n:
                print(count)
                return
        count += b_a_sum[j]
        i += 1

    print(count)

if __name__ == '__main__':
    submit()
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
A = sorted(A)[:: -1]


L=[0]*N
R=[0]*N
L[0]=A[0]
R[0]=A[N-1]

for n in range(1,N):
  L[n]=gcd(A[n],L[n-1])
  R[n]=gcd(A[N-n-1],R[n-1])
  
  ans=max(L[N-2],R[N-2])

for i in range(1,N-1):
  ans=max(ans,gcd(L[i-1],R[N-i-2]))

print(ans)

### FIXED CODE ###

A,B,T=map(int, input().split())

print(int((T+0.5)//A*B))
import sys
from collections import deque
from numba import jit

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

@jit
def gg(nn, x, y, n, is_sit):
	q = deque()
	q.append(1000*x+y)
	cl = set()
	cl.add(x*1000+y)
	while not q.empty():
		v = q.popleft()
		x,y = v//1000, v %1000
		nn[x][y] -= 1
		k = nn[x][y]
		for dx,dy in ([-1,0], [0,-1], [1,0], [0,1]):
			if x+dx < 0 or x +dx >= n or y + dy < 0 or y + dy >= n:
				continue
			if nn[x+dx][y + dy] <= k + is_sit[x+dx][y+dy]:
				continue
			if (x+dx)*1000+(y+dy) in cl:
				continue
			q.append((x+dx)*1000+ (y+dy))
			cl.add((x+dx)*1000 + (y+dy))
		#print('yyyyyy')
		#for l in nn:
		#	print(l)

def main():
	n = int(input())
	nn = [[(n+1)//2] * n for _ in range(n)]
	is_sit = [[1] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			nn[i][j] = min(i+1,j+1,n-i,n-j)
	#for l in nn:
	#	print(l)
	
	#b , c = tin()
	pl = lin()
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]-1
		is_sit[x][y] = 0
		gg(nn, x, y, n, is_sit)
		
	print(ans)
	#s = input()
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

#+++++

def main():
	n = int(input())
	nn = [[min(i,j,n-i-1,n-j-1) for j in range(n)] for i in range(n)]
	is_sit = [[True] * n for _ in range(n)]
	cc = [[0]*n for _ in range(n)]
	
	#b , c = tin()
	pl = list(map(int, input().split()))
	ans = 0
	for p in pl:
		x, y = (p-1) // n, (p-1) % n
		ans += nn[x][y]
		is_sit[x][y] = False
		q = [(x, y, nn[x][y])]
		while q:
			(x, y, v) = q.pop()
			if x >= 0 and nn[x-1][y]>v:
				nn[x-1][y] = v
				q.append((x-1, y, v+is_sit[x-1][y]))
			if x < n-1 and nn[x+1][y]>v:
				nn[x+1][y] = v
				q.append((x+1, y, v+is_sit[x+1][y]))		
			if y >= 0 and nn[x][y-1]>v:
				nn[x][y-1] = v
				q.append((x, y-1, v+is_sit[x][y-1]))
			if y < n-1 and nn[x][y+1]>v:
				nn[x][y+1] = v
				q.append((x, y+1, v+is_sit[x][y+1]))	
		
	print(ans)
	#s = input()	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
k = int(input())
a, b = map(int,input().split())
x = k * (a // k) + k
if k == 1:
    print("OK")
elif : x >= a and x <= b:
    print("OK")
else:
    print("NG")

### FIXED CODE ###

k = int(input())
a, b = map(int,input().split())
for i in range(a, b+1):
    if i%k == 0 :
        print("OK")
        break
else:
    print("NG")
import bisect
a,b,q=map(int,input().split())
S=[];T=[]
for _ in range(a):
    s=int(input())
    S.append(s)
for _ in range(b):
    t=int(input())
    T.append(t)
S.append(10**12)
T.appent(10**12)

for _ in range(q):
    x=int(input())
    idx_s=bisect.bisect_left(S,x)
    idx_t=bisect.bisect_left(T,x)
    se=S[idx_s]
    sw=S[idx_s-1]
    te=T[idx_t]
    tw=T[idx_t-1]

    m1=abs(x-se)+abs(se-te)
    m2=abs(x-se)+abs(se-tw)
    m3=abs(x-sw)+abs(sw-te)
    m4=abs(x-sw)+abs(sw-tw)
    m5=abs(x-te)+abs(te-se)
    m6=abs(x-te)+abs(te-sw)
    m7=abs(x-tw)+abs(tw-se)
    m8=abs(x-tw)+abs(tw-sw)
    print(min(m1,m2,m3,m4,m5,m6,m7,m8)) 
    




### FIXED CODE ###

import bisect
a,b,q=map(int,input().split())
S=[];T=[]
for _ in range(a):
    s=int(input())
    S.append(s)
for _ in range(b):
    t=int(input())
    T.append(t)
S.append(10**12)
T.append(10**12)

for _ in range(q):
    x=int(input())
    idx_s=bisect.bisect_left(S,x)
    idx_t=bisect.bisect_left(T,x)
    se=S[idx_s]
    sw=S[idx_s-1]
    te=T[idx_t]
    tw=T[idx_t-1]

    ans=float("inf")
    for ss in [se,sw]:
        for tt in [te,tw]:
            ans=min(ans,abs(ss-x)+abs(tt-ss),abs(tt-x)+abs(tt-ss))
    print(ans)
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    dp=[1 for i in range(n)]
    dp[0]=0
    dp[1]=0
    for i in range(3,n):
        for j in range(i-2):
            dp[i]=(dp[i]+dp[j])%mod
    #print(dp)
    print(dp[-1]%mod)
    

        
        
        
        
    
if __name__=="__main__":
    main()



### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    dp=[1 for i in range(n)]
    dp[0]=0
    if n==1:
        print(0)
        sys.exit()
    dp[1]=0
    for i in range(3,n):
        for j in range(i-2):
            dp[i]=(dp[i]+dp[j])%mod
    #print(dp)
    print(dp[-1]%mod)
    

        
        
        
        
    
if __name__=="__main__":
    main()
import math as mt
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
#print(A)
S = 0
P2 = mt.floor(N/2 - 1)
if N % 2 == 0:
    for i in range(0,P2,1):
        S += 2 * (A[N-i-1] - A[i])
    S += A[P2+1] - A[P2]
elif N % 4 == 1:
    for i in range(0,P2,1):
        S += 2 * (A[N-i-1] - A[i])
    S += 2 * A[N-1-P2] - A[P2] - A[P2+1]
else:
    for i in range(0,P2,1):
        S += 2 * (A[N-i-1] - A[i])
    S += A[N-P2-1] + A[N-P2] - 2 * A[P2]
print(S)


### FIXED CODE ###

import math as mt
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
#print(A)
S = 0
P2 = mt.floor(N/2 - 1)
if N % 2 == 0:
    for i in range(0,P2,1):
        S += 2 * (A[N-i-1] - A[i])
    S += A[P2+1] - A[P2]
    print(S)
elif N % 2 == 1:
    for i in range(0,P2,1):
        S += 2 * (A[N-i-1] - A[i])
    S1 = A[N-P2-2] + A[N-P2-1] - 2 * A[P2]
    S2 = 2 * A[N-1-P2] - A[P2] - A[P2+1]
    if S1 >= S2:
        print(S1+S)
    else:
        print(S2+S)
s,t = map(int,input().split())
a,b = map(int,input().split())
u =map(int,input().split())

if s==u:
  print( a-1,b)
else:
  print( a,b-1)

### FIXED CODE ###

s,t = map(str,input().split())
a,b = map(int,input().split())
u =input()

if u==s:
  a -=1
else:
  b -=1
  
print(a,b)
if(h==1)or (w==1):
    print(1)
elif (h*w)%2==0:
    print(int(h*w/2))
else:
    print(int((h*w+1)/2))




### FIXED CODE ###

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

if((h==1)or(w==1)):
    print(1)
elif (h*w)%2==0:
    print(int(h*w/2))
else:
    print(int((h*w+1)/2))
from collections import*
import sys
input = sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        # 親の番号を格納する。親だった場合は-(その集合のサイズ)
        # 作るときはParentsの値を全て-1にする
        # こうすると全てバラバラになる
        self.parents = [-1 for i in range(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
        return

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


n, k, l = map(int, input().split())
w = [list(map(int, input().split())) for i in range(k+l)]
ro = w[:k]
ra = w[l:]

ro_cl = UnionFind(n)
ra_cl = UnionFind(n)
d = defaultdict(int)

for p, q in ro:
    ro_cl.union(p-1, q-1)
for p, q in ra:
    ra_cl.union(p-1, q-1)

for i in range(n):
    d[(ro_cl.find(i), ra_cl.find(i))] += 1
print(*[d[(ro_cl.find(i), ra_cl.find(i))]for i in range(n)])

### FIXED CODE ###

c = input()
p = "aeiou"
if c in p:
    print("vowel")
else:
    print("consonant")
class Sort():
	def __init__(self,n,cards):
		self.cards = cards
		self.n = n

	def bubble_sort(self):
		# bubble sort
		flag = 1
		while flag != 0:
			flag = 0
			rev = list(range(1,self.n))
			rev.reverse()
			for j in rev:
				if int(self.cards[j][1]) < int(self.cards[j-1][1]):
					self.cards[j],self.cards[j-1] = self.cards[j-1],self.cards[j]
					flag = 1

	def select_sort(self):
		for i in range(self.n):
			mini = i
			for j in range(i,self.n):
				if int(self.cards[j][1]) < int(self.cards[mini][1]):
					mini = j
			if i != mini:
				self.cards[i],self.cards[mini] = self.cards[mini],self.cards[i]

	def check_stable(self,origin):
		check_org = [["" for i in range(self.n)] for k in range(9)]
		check_sort = [["" for i in range(self.n)] for k in range(9)]
		for i in range(self.n):
			check_org[int(origin[i][1])-1][i] = origin[i][0]
			check_sort[int(self.cards[i][1])-1][i] = self.cards[i][0]
		flag = 0
		for i in range(self.n):
			if "".join(check_org[i]) != "".join(check_sort[i]):
				flag = 1
				break

		if flag == 0:
			print("Stable")
		else:
			print("Not stable")

	def print_card(self):
		for i in range(self.n):
			if i != self.n-1:
				print("%s" % (self.cards[i]),end=" ")
			else:
				print("%s" % (self.cards[i]))

if __name__ == '__main__':
	n = int(input())
	card = input().split()
	card2 = card.copy()
	card_origin = card.copy()
	
	bubble = Sort(n,card)
	bubble.bubble_sort()
	bubble.print_card()
	bubble.check_stable(card_origin)
	
	select = Sort(n,card2)
	select.select_sort()
	select.print_card()
	select.check_stable(card_origin)


### FIXED CODE ###

class Sort():
	def __init__(self,n,cards):
		self.cards = cards
		self.n = n

	def bubble_sort(self):
		# bubble sort
		flag = 1
		while flag != 0:
			flag = 0
			rev = list(range(1,self.n))
			rev.reverse()
			for j in rev:
				if int(self.cards[j][1]) < int(self.cards[j-1][1]):
					self.cards[j],self.cards[j-1] = self.cards[j-1],self.cards[j]
					flag = 1

	def select_sort(self):
		for i in range(self.n):
			mini = i
			for j in range(i,self.n):
				if int(self.cards[j][1]) < int(self.cards[mini][1]):
					mini = j
			if i != mini:
				self.cards[i],self.cards[mini] = self.cards[mini],self.cards[i]

	def check_stable(self,origin):
		check_org = [["" for i in range(self.n)] for k in range(9)]
		check_sort = [["" for i in range(self.n)] for k in range(9)]
		for i in range(self.n):
			check_org[int(origin[i][1])-1][i] = origin[i][0]
			check_sort[int(self.cards[i][1])-1][i] = self.cards[i][0]
		flag = 0
		for i in range(9):
			if "".join(check_org[i]) != "".join(check_sort[i]):
				flag = 1
				break

		if flag == 0:
			print("Stable")
		else:
			print("Not stable")

	def print_card(self):
		for i in range(self.n):
			if i != self.n-1:
				print("%s" % (self.cards[i]),end=" ")
			else:
				print("%s" % (self.cards[i]))

if __name__ == '__main__':
	n = int(input())
	card = input().split()
	card2 = card.copy()
	card_origin = card.copy()
	
	bubble = Sort(n,card)
	bubble.bubble_sort()
	bubble.print_card()
	bubble.check_stable(card_origin)
	
	select = Sort(n,card2)
	select.select_sort()
	select.print_card()
	select.check_stable(card_origin)
Row = int(input())
List = []
for i in range (Row):
  List.append(list(map(str, input().split())))
res = 0
for i in range(Row):
  if List[i][1] = "JPY":
    res += int(List[i][0])
  else:
    res += int(List[i][0])*380000
print(res)

### FIXED CODE ###

Row = int(input())
List = []
for i in range (Row):
  List.append(list(map(str, input().split())))
res = 0
for i in range(Row):
  if List[i][1] == "JPY":
    res += float(List[i][0])
  else:
    res += float(List[i][0])*380000
print(res)
X = int(input())
lists = []
max = 1
for i in range(1,X+1):
    for j in range(2,X+1):
        if i**j <= X:
           lists.append(i**j)
lists.sort()
print(lists[-1])



### FIXED CODE ###

X = int(input())
lists = []
max = 1
for i in range(1,X+1):
    for j in range(2,X+1):
        if i**j <= X:
            if max < i**j:
                max = i**j
        elif i**j > X:
            break
print(max)
n,k-map(int,input().split())
ans=k
for i in range(n):
	ans*=k-1
print(ans)

### FIXED CODE ###

a,b,c=input().split()
if a!=b and b!=c and c!=a:
	print(3)
elif a!=b or b!=c or c!=a:
	print(2)
else:
	print(1)
import math
x1,y1,x2,y2=map(float,input().split())
x2=x2-x1
y2=y2-y1
x1,y1=0,0
dis=(x2**2+y2**2)
print(math.sqrt(dis))

### FIXED CODE ###

import math
a,b,c=map(float,input().split())
c=math.radians(c)
h=b*math.sin(c)
s=a*h/2
d=math.sqrt(a**2+b**2-2*a*b*math.cos(c))
l=a+b+d
print(s,l,h)
import sys
import time
import math
st = time.perf_counter()
def inpl():
    return list(map(int, input().split()))
# ------------------------------

N = int(input())
nl = [0] * 10101
ls = inpl()
ans = 0
for i in ls:
	nl[i] += 1
	ans += i
M = int(input())
for _ in range(M):
	a, b = map(int, input().split())
	ans = ans - (nl[a] * a) + (nl[a] * b)
	nl[b] += nl[a]
	nl[a] = 0
	print(ans)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)


### FIXED CODE ###

import sys
import time
import math
st = time.perf_counter()
def inpl():
    return list(map(int, input().split()))
# ------------------------------

N = int(input())
nl = [0] * 100100
ls = inpl()
ans = 0
for i in ls:
	nl[i] += 1
	ans += i
M = int(input())
for _ in range(M):
	a, b = map(int, input().split())
	ans = ans - (nl[a] * a) + (nl[a] * b)
	nl[b] += nl[a]
	nl[a] = 0
	print(ans)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)
S = int(input())
mod = 10**9 + 7

dp = [0] * (S+1)
dp[0] = 1
for i in range(1, S+1):
    for j in range((i+3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])


### FIXED CODE ###

S = int(input())
mod = 10**9 + 7

dp = [0] * (S+1)
dp[0] = 1
for i in range(1, S+1):
    for j in range((i-3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])
def saiki(visited, inv, path, nows):
  buf = []
  for now in nows:
    for p in path[now]:
      if p not in visited:
        buf.append(p)
        visited.append(p)
        inv[p-2]=now
  if len(buf)==0:
    return
  saiki(visited, inv, path, buf)
  
N, M = map(int, input().split())

inv = [i for i in range(N-1)]
visited = [1]

path = {i :[] for i in range(1, N+1)}
for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
saiki(visited, inv, path, [1])
print("Yes")
for i in inv:
  print(i)


### FIXED CODE ###

import queue

q = queue.Queue()
N, M = map(int, input().split())

ans = [-1 for i in range(N+1)]
path = [[] for i in range(N+1)]

for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
q.put(1)
COUNTER = 0
while not q.empty() :
  now = q.get()
  for p in path[now]:
    if ans[p]==-1:
      ans[p]=now
      q.put(p)
      #print(COUNTER, now,p)
      COUNTER+=1
      
print("Yes")
for i in ans[2:]:
  print(i)
IN = iter(Input.split('\n')).__next__
def input():
    return IN()
#ここから先

S=input()
T=[]

l=-1
while l>=-len(S):
    if S[l]=="r":
        if l-2<-len(S):
            print("NO");break
        elif S[l-2]=="s":
            T+="eraser"[::-1]
            l-=6
        else:
            T+="dreamer"[::-1]
            l-=7
    elif S[l]=="e":
        T+="erase"[::-1]
        l-=5
    elif S[l]=="m":
        T+="dream"[::-1]
        l-=5
    else:
        print("NO");break
        
if S=="".join(T[::-1]):
    print("YES")


### FIXED CODE ###

S=input()
T=[]

l=-1
while l-2>=-len(S):
    k=S[l:l-3:-1]
    if k=="mae":
        T+="dream"[::-1]
        l-=5
    elif k=="rem":
        T+="dreamer"[::-1]
        l-=7
    elif k=="esa":
        T+="erase"[::-1]
        l-=5
    elif k=="res":
        T+="eraser"[::-1]
        l-=6
    else:
        break
if S=="".join(T[::-1]):
    print("YES")
else:
    print("NO")
lst = list(map(int, input()))
n = len(lst) - 1
op_lst = ["+", "-"]
for i in range(2**n):
    op = ["-"] * 3
    for j in range(n):
        if ((i >> j) & 1):
            op[n-j-1] = op_lst[0]
    formula = ""
    for num,opp in zip(lst, op + [""]):
        formula += (num + opp)
    if eval(formula) == 7:
        print(formula + "=7")
        break

### FIXED CODE ###

lst = list(map(str, input()))
n = len(lst) - 1
op_lst = ["+", "-"]
for i in range(2**n):
    op = ["-"] * 3
    for j in range(n):
        if ((i >> j) & 1):
            op[n-j-1] = op_lst[0]
    formula = ""
    for num,opp in zip(lst, op + [""]):
        formula += (num + opp)
    if eval(formula) == 7:
        print(formula + "=7")
        break
#問題D
#これだとタイムアウト
import warnings
warnings.filterwarnings('ignore')
import pandas as pd
import numpy as np

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])

### FIXED CODE ###

#問題D
#これだとタイムアウト
import numpy as np
import warnings
warnings.filterwarnings('ignore')

N, W = list(map(int, input().split()))
w = np.array([0] * (N+1))
v = np.array([0] * (N+1))
for i in range(N):
    w[i+1], v[i+1] = map(int, input().split())

dp = np.array([[0] * (W+1)] * (N+1))
for i in range(1, N+1):
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr = np.zeros(W + 1, dtype=int)
    tmp_arr[w[i]:] = dp[i-1][:-w[i]] + v[i]
    dp[i] = np.maximum(dp[i-1], tmp_arr)

print(dp[N, W])
n = input()
a = [int(i) for i in input.solit()]
X = 0
ans = 0
for i in a:
	X += i
    if X > 0:
      b = -1 - X
      ans += b - a(i+1)
    else X < 0:
      b = 1 - X
      ans += b - a(i+1)
    return ans
print (ans)

### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))