Harryxun/stf_run huggingface dataset:
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), sys.stdin.readline().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), sys.stdin.readline().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v3_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

### FIXED CODE ###

import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)
n = int(input())
ai = list(map(int,input().split()))

def dp(i, j):
	if i==0 and j==0:
		return 0
	elif i == 0 and j==1:
		return -10**9
	elif j==0:
		return max(dp(i-1,0)+ai[i-1], dp(i-1,1)-ai[i-1])
	else:
		return max(dp(i-1,0)-ai[i-1], dp(i-1,1)+ai[i-1])

print(dp(n,0))

### FIXED CODE ###

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

dp =[[0, -10**9]]
#print(dp[0][0])

for i in range(1,n+1):
	dp.append([max(dp[i-1][0]+ai[i-1], dp[i-1][1]-ai[i-1]), \
			max(dp[i-1][0]-ai[i-1], dp[i-1][1]+ai[i-1])])
	#print(dp)
    
print(dp[n][0])
#ABC077C
N=int(input())
#大きい順に# 並べる
A=sorted(list(map(int,input().split())), reverse=True)
B=sorted(list(map(int,input().split())), reverse=True)
C=sorted(list(map(int,input().split())), reverse=True)
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    if j > 0:
        if B[i] == B[i-1]:
            C_under_B[i]=C_under_B[i-1]
            continue
    for j in range(N):
        if C[j]>B[i]:
            C_under_B[i]+=1
        else:       #C[j+1]>C[j]>B[i]なので検討を中止する
            break
#あるAの下にいくつBが入るか数える
B_under_A=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    if j > 0:
        if A[i] == A[i-1]:
            B_under_A[i]=B_under_A[i-1]
            continue
    for j in range(N):
        if B[j]>A[i]:
            B_under_A[i]+=1
        else:       #B[j+1]>B[j]>A[i]なので検討を中止する
            break
#あるAのもとに入るBのもとに入るCを数える
C_under_B_under_A=[0]*N
for i in range(N):
    C_under_B_under_A[i]=sum([C_under_B[j] for j in range(B_under_A[i])])
#出力
print(sum(C_under_B_under_A))


### FIXED CODE ###

#ABC077C 解説を見て自作
import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    C_under_B[i]=N-bisect.bisect_right(C,B[i])
#あるBの上にいくつAが乗るか数える
A_on_B=[0]*N     #i番目のBの上に乗るAの数
for i in range(N):
    A_on_B[i]=bisect.bisect_left(A,B[i])
#あるBの上下におけるものを数えて出力
ans=0
for i in range(N):
    ans+=C_under_B[i]*A_on_B[i]
print(ans)
(a, b) = [int(i) for i in input().split]
print(a * 2, (a + b) * 2)

### FIXED CODE ###

x = input().split()
a = int(x[0])
b = int(x[1])
print(a*b, (a+b)*2)
xlist=[]
for a in range(10):
    for b in range(10):
        xlist.append(a*b)

if n in xlist:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

N=int(input())

list=[]
for i in range(1,10):
  for j in range(1,10):
    list.append(i*j)
if N in list:
  print("Yes")
else:
  print("No")
n, k = map(int, input().split())
h = list(map(int, input().split()))
         
         count = 0
         
         for i in h:
         if i >= k:
         count += 1
         
         print(count)

### FIXED CODE ###

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

count = 0

for i in h:
   if i >= k:
       count += 1

print(count)
x,y = int(input())
while True
    if x == y:
        break
    elif x < y:
        print(x,y)
    else:
        print(y,x)
        


### FIXED CODE ###

while True:
    x,y = map(int,input().split())

    if x == 0 and y == 0:
        break
    elif x < y:
        print(x,y)
    else:
        print(y,x)
r = map(int, input().split())

print(3*r*r)

### FIXED CODE ###

r = int(input())

print(3*r*r)
R = input()
S = R*3.14*2
print(S.float)

### FIXED CODE ###

import math
R = int(input())
print(2*math.pi*R)
s=input()
t=input()
sz=len(t)
ans=100000000000
for i in range(0,len(s)-sz):
    k=s[i:i+sz]
    c=0
    for j in range(sz):
        if k[j]==t[j]:
            c+=1
        else:
            ans=min(ans,sz-c)
    # print(c)
ans=min(ans,sz-c)
print(ans)


### FIXED CODE ###

s=input()
t=input()
sz=len(t)
ans=100000000000
c=0
if len(s)==sz:
    c=0
    for j in range(sz):
        if s[j]==t[j]:
            c+=1
        else:
            ans=min(ans,sz-c)
else:
    for i in range(0,len(s)-sz):
        k=s[i:i+sz]
        c=0
        for j in range(sz):
            if k[j]==t[j]:
                c+=1
            else:
                ans=min(ans,sz-c)
        # print(c)
ans=min(ans,sz-c)
print(ans)
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))


### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())
print(A * B // gcd(A, B))
import math

A, B, C, D = (int(i) for i in input().split())


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


one_to_b = B - ((B // C) + (B // D) - (B // lcm(C, D)))
one_to_a = A - 1 - ((((A - 1) // C) +
                     ((A - 1) // D) -
                     (A - 1) // lcm(C, D)))

print(one_to_b - one_to_a)


### FIXED CODE ###

import fractions

A, B, C, D = (int(i) for i in input().split())


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


one_to_b = B - ((B // C) + (B // D) - (B // lcm(C, D)))
one_to_a = A - 1 - ((((A - 1) // C) +
                     ((A - 1) // D) -
                     (A - 1) // lcm(C, D)))

print(one_to_b - one_to_a)
import math

N = int(input())
ans = 0
for k in range(1, int(math.sqrt(N)) + 1):
  if N % k == 0:
    m = int(N / k) - 1 
    ans += m if N % m == N // m else 0
print(ans)

### FIXED CODE ###

import math

N = int(input())
ans = 0
for k in range(1, int(math.sqrt(N)) + 1):
  if N % k == 0:
    m = int(N / k) - 1
    if m == 0:
      continue
    ans += m if N % m == N // m else 0
print(ans)
import time, math

def f(a):
    M=10**9+7
    ans, z = 0, 1
    for x in a:
        z = (z * x) // math.gcd(z, x)
    #print(z)
    z %= M
    for x in a:
        ans += z * pow(x, M-2, M)
        ans %= M
    return ans

n = input()
a = list(map(int, input().split()))
#a = []
#for i in range(1000):
#    a.append(1000000-i)
print(f(a))


### FIXED CODE ###

import time, math
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def f(a):
    M=10**9+7
    ans, z = 0, 1
    for x in a:
        z = (z * x) // gcd(z, x)
    #print(z)
    z %= M
    for x in a:
        ans += z * pow(x, M-2, M)
        ans %= M
    return ans

n = input()
a = list(map(int, input().split()))
#a = []
#for i in range(1000):
#    a.append(1000000-i)
print(f(a))
n=int(input())
x=[0 for i in range(7)]
while True:
  if n==0:
    break
  for i in range(n):
    a=int(input())
    if 0<=a<10:
      x[0]+=1
    elif 10<=a<20:
      x[1]+=1
    elif 20<=a<30:
      x[2]+=1
    elif 30<=a<40:
      x[3]+=1
    elif 40<=a<50:
      x[4]+=1 
    elif 50<=a<60:
      x[5]+=1
    else:
      x[6]+=1
  for i in range(7):
    if x[i]==0:
      print(0)
    else:
      print(x[i])


### FIXED CODE ###

while True:
  x=[0 for i in range(7)]
  n=int(input())
  if n==0:
    break
  for i in range(n):
    a=int(input())
    if 0<=a<10:
      x[0]+=1
    elif 10<=a<20:
      x[1]+=1
    elif 20<=a<30:
      x[2]+=1
    elif 30<=a<40:
      x[3]+=1
    elif 40<=a<50:
      x[4]+=1 
    elif 50<=a<60:
      x[5]+=1
    else:
      x[6]+=1
  for i in range(7):
    print(x[i])
#sになるのがちょうどk個
n,k,s=map(int,input().split())
ans=0
n_max=10**5
ans=[0]*n
moto=[]
detarame=10**5-1
if s<n:
    ans = [n]*k +[n+1]*(n-k)
    print(ans)
else:
    flag=0
    remain=s
    for i in range(n):
        moto.append(min(n_max,remain))
        if moto[-1]<n_max:
            flag=1
            break
        remain-=moto[-1]
    nagasa=len(moto)
    for i in range(nagasa+k-1):
        ans[i]=moto[i%nagasa]
    for i in range(nagasa+k-1,n):
        ans[i]=detarame
    print(ans)

### FIXED CODE ###

#sになるのがちょうどk個
n,k,s=map(int,input().split())
ans=[0]*n
if s==10**9:
    ans = [s]*k +[10**9-1]*(n-k)
else:
    ans = [s]*k + [10**9]*(n-k)
print(*ans, sep=' ')
int a
str s
a = int(input())
s = str(input())

if a>=3200:
  print("s")
  else :
    print("red")


### FIXED CODE ###

a = int(input())
s = input()

if a>=3200:
	print(s)
else :
	print("red")
r = int(input())
p = 3.141592653589
a = r * r * p
b = 2 * r * p
print("{0:.6f} {1:.6f}".format(a,b))

### FIXED CODE ###

r = float(input())
p = 3.141592653589
a = r * r * p
b = 2 * r * p
print("{0:.6f} {1:.6f}".format(a,b))
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

a_dict={}
for i in range(h):
  a=lnii()
  for j in range(w):
    a_dict[a[j]]=(i,j)

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<=h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)
,c,d,=map(int,input().split())
def func(a,b,c,d):
    while a>=0 and c>=0:
        c-=b
        a-=d
    return "Yes" if a>=c else "No"
print(func(a,b,c,d))

### FIXED CODE ###

a,b,c,d,=map(int,input().split())
def func(a,b,c,d):
    while a>0 and c>0:
        c-=b
        if c<=0:
            return "Yes"
        a-=d
        if a<=0:
            return "No" 
print(func(a,b,c,d))
import numpy as np

N, W = map(int, input().split())
wv = [[0,0]]
for _ in range(N):
    wv.append( list(map(int, input().split())))
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    for w_lim in range(1,W+1):
        if w_lim - wv[n][0] >= 0 :
            dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
        else :
            dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])


### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
dp = np.array([ [0]*(W+1) ] * (N+1))
for n in range(1,N+1):
    w, v = map(int, input().split() )
    dp[n][:] = dp[n-1][:]
    dp[n][w:W+1] = np.maximum(dp[n-1][w:W+1], dp[n-1][:W+1-w]+v )
    # for w_lim in range(1,W+1):
    #     if w_lim - wv[n][0] >= 0 :
    #         dp[n][w_lim] = max( dp[n-1][w_lim], dp[n-1][w_lim-wv[n][0]]+wv[n][1] )
    #     else :
    #         dp[n][w_lim] = dp[n-1][w_lim]
print(dp[N][W])
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  string S;
  ll K;
  cin >> S >> K;
  smatch m;
  regex_match(S, m, regex("^(1*)([1-9]*)$"));
  cout << ((m.length(1) >= K) ? '1' : m.str(2).front()) << endl;
  return 0;
}


### FIXED CODE ###

import re

S = input()
K = int(input())

m = re.match(r'\A(1+)([1-9]*)\Z', S)
if m:
    print('1' if len(m.group(1)) >= K else m.group(2)[0])
else:
    print(S[0])
if(a+b+c >=22):
    print bust
else:
    print win

### FIXED CODE ###

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

if (a+b+c >= 22):
    print("bust")
else:
    print("win")
L,R,d = input(int(_) for _ in input().split())

for i in range(0, d):
  if(i%d == 0) cnt++
  
print(cnt)

### FIXED CODE ###

L,R,d=map(int, input().split())
cnt=0
 
for i in range(L, R+1):
  if i%d == 0: cnt+=1
  
print(cnt)
N,K = list(map(int,input().split()))
s = input()

a = []
b = []

index = 0
length = 0
judge = "0"
for i in range(len(s)):
	if s[i] == judge:
		length += 1
	if s[i] != judge:
		if judge == "0":
			b.append(length)
		if judge == "1":
			a.append(length)
		length = 1
		judge = str((int(judge)+1)%2)
if judge == "0":
	b.append(length)
if judge == "1":
	a.append(length)


if len(a) == len(b):
	M = len(a)
	if K >= M:
		print(len(s))
		exit()
	
	ans = 0
	ans_new = 0
	for i in range(K):
		ans += a[i]+b[i]
	ans_max = ans
	for i in range(M-K):
		if i == 0:
			ans_new = ans-b[0]+b[K]+a[K]
		if i != 0:
			ans_new = ans-a[i-1]-b[i]+b[K+i]+a[K+i]
		ans_max = max(ans_max,ans_new)
		ans = ans_new
	print(ans_max)
	exit()
	
if len(a) < len(b):
	M = len(b)
	if K >= M:
		print(len(s))
		exit()
	
	ans = 0
	for i in range(K):
		ans += a[i]+b[i]
	ans_max = ans
	for i in range(M-K+1):
		if i == 0:
			if M-1 <= K:
				ans_new = ans-b[0]+b[K]
			else:
				ans_new = ans-b[0]+b[K]+a[K]
		if i == M-K:
			ans_new = ans-a[M-K-1]-b[M-K]+b[M-1]
		if i != 0 and i != M-K:
			ans_new = ans-a[i-1]-b[i]+b[K+i]+a[K+i]
		
		ans_max = max(ans_max,ans_new)
		ans = ans_new
	print(ans_max)
	exit()



### FIXED CODE ###

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

a = []
b = []

index = 0
length = 0
judge = "0"
for i in range(len(s)):
	if s[i] == judge:
		length += 1
	if s[i] != judge:
		if judge == "0":
			b.append(length)
		if judge == "1":
			a.append(length)
		length = 1
		judge = str((int(judge)+1)%2)
if judge == "0":
	b.append(length)
	a.append(0)
if judge == "1":
	a.append(length)


M = len(a)
if K >= M:
	print(len(s))
	exit()

ans = 0
ans_new = 0
for i in range(K):
	ans += a[i]+b[i]
ans_max = ans
for i in range(M-K):
	if i == 0:
		ans_new = ans-b[0]+b[K]+a[K]
	if i != 0:
		ans_new = ans-a[i-1]-b[i]+b[K+i]+a[K+i]
	ans_max = max(ans_max,ans_new)
	ans = ans_new
print(ans_max)
import numpy as np

L, R = map(int, input().split())

# mod 2019 の答えは 0 ~ 2018 のいずれか
# それぞれのmodを取った積のmodでも同じ
np_nums = np.sort(np.mod(np.arange(L, R + 1), 2019))


def get_ans():
    # mod後の最小値コンビを十分大きな値で初期化しておく
    nums = [2019, 2020]
    for n in range(L, R + 1):
        mod = n % 2019
        # 0が来た瞬間終了
        if mod == 0:
            return 0

        # 最小値コンビの内どっちかより小さいなら置き換える
        if nums[0] > n:
            nums[0] = n
        elif nums[1] > n:
            nums[1] = n

    # ループ終わったら最小値コンビの積のmodを取る
    return (nums[0] * nums[1]) % 2019


print(get_ans())

### FIXED CODE ###

L, R = map(int, input().split())

# n mod 2019 の答えは 0 ~ 2018 のいずれか
# それぞれのmodを取った積のmodでも同じ答えになる


def get_ans():
    # 差が2018以上なら積が0の組み合わせが存在する
    if R - L >= 2018:
        return 0

    # 総当たり
    ans = 2019
    for X in range(L, R):
        for Y in range(X + 1, R + 1):
            ans = min((ans, (X * Y) % 2019))

    return ans


print(get_ans())
import numpy as np

N, K, Q = map(int, input().split())

points = np.array([K for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] += 1

for n in range(N):
    if points[n] < 1:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K, Q = map(int, input().split())

points = np.array([K - Q for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points[A] +=1

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')
H,W = map(int, input().split())

C = [input() for i in range(W)]

for i in range(W):
    print(C[i])
    print(C[i])

### FIXED CODE ###

H,W = map(int, input().split())

for i in range(H):
    x = input()
    print(x)
    print(x)
n = int(input())
l = [input() for i in range(n)]
a = 0
b = 0
ba = 0
ab = 0
for i in range(n):
    if 'AB' in l[i]:
        for j in range(len(l[i])-1):
            if l[i][j] == 'A' and l[i][j+1] == 'B':
                ab += 1
    if l[i][0] =='B' and l[i][-1] == 'A':
        ba += 1
    elif l[i][-1] == 'A':
        a += 1
    elif l[i][0] == 'B':
        b += 1
if max(a,b) == 0　and ba <= 1:
    print(ab)
elif max(a,b) == 0
    print((ab+ba-1))
else:
    print(min(a,b)+ab+ba)

### FIXED CODE ###

n = int(input())
l = [input() for i in range(n)]
a = 0
b = 0
ba = 0
ab = 0
for i in range(n):
    if 'AB' in l[i]:
        for j in range(len(l[i])-1):
            if l[i][j] == 'A' and l[i][j+1] == 'B':
                ab += 1
    if l[i][0] =='B' and l[i][-1] == 'A':
        ba += 1
    elif l[i][-1] == 'A':
        a += 1
    elif l[i][0] == 'B':
        b += 1
if max(a,b) == 0 and ba <= 1:
    print(ab)
elif max(a,b) == 0:
    print(ab+ba-1)
else:
    print(min(a,b)+ab+ba)
n, *A = map(int, open(0).read().split())
B = [A[0]]
C = [A[0]]
D = [0]
for i in range(1, n):
  if (C[i-1] + A[i]) * C[i-1] < 0:
    B.append(A[i])
    C.append(C[i-1] + A[i])
    D.append(D[i-1])
  else:
    if C[i-1] > 0:
      B.append(-(C[i-1]+1))
      C.append(-1)
      D.append(C[i-1]+1 + A[i])
    elif C[i-1] < 0:
      B.append(-C[i-1]+1)
      C.append(1)
      D.append(-C[i-1]+1 + A[i])
print(A)
print(B)
print(C)
print(D)

### FIXED CODE ###

from itertools import accumulate
n, *A = map(int, open(0).read().split())
B = list(accumulate(A))
p0 = n0 = p1 = n1 = 0
for i, b in enumerate(B):
    if i % 2 == 0:
        if b+p0-n0 <= 0:
            p0 += abs(b+p0-n0)+1
        if b+p1-n1 >= 0:
            n1 += abs(b+p1-n1)+1
    else:
        if b+p0-n0 >= 0:
            n0 += abs(b+p0-n0)+1
        if b+p1-n1 <= 0:
            p1 += abs(b+p1-n1)+1
print(min(p0+n0, p1+n1))
a,b=map(int,input().split())

import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
  
print(lcm(a,b))

### FIXED CODE ###

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

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
  
print(lcm(a,b))
def dfs(i,f):
  if i == n-1:
    return sum(list(map(int,f.split("+"))))
  return dfs(i+1,f+s[i+1])+\dfs(i+1,f+"+"+s[i+1])
  
s= input()
n=len(s)
print(dfs(0,s[0]))


### FIXED CODE ###

s=input()
n=len(s)
ans=0

for i in range(1<<(n-1)):
  f=s[0]
  for j in range(n-1):
    if i&(1<<j):
      f += "+"
    f+= s[j+1]
  ans += sum(map(int, f.split("+")))
  
print(ans)
n = int(input())
s = list(input())
ans = [i * 0 for i in range(51)]
for i in range(n-1):
    tmp1 = list(set(s[:i+1]))
    tmp2 = list(set(s[i:]))
    for j in range(len(tmp1)):
        if tmp1[j] in tmp2:
            ans[i] += 1
print(max(ans))


### FIXED CODE ###

n = int(input())
s = list(input())
ans = [i * 0 for i in range(100)]
if n == 2:
    ans.clear()
    if s[0] == s[1]:
        ans.append(1)
    else:
        ans.append(0)
else:
    for i in range(0,n-1):
        tmp1 = list(set(s[:i]))
        tmp2 = list(set(s[i:]))
        for j in range(len(tmp1)):
            if tmp1[j] in tmp2:
                ans[i] += 1
print(max(ans))
ans = 0
n = int(input())
blue = [input() for i in range(n)]
m = int(input())
red = [input() for i in range(m)]
for i in range(m):
    if red[m] in blue:
        blue.remove(red[m])
for j in list(set(blue)):
    if blue.count(j) > ans:
        ans = blue.count(j)
print(ans)


### FIXED CODE ###

ans = 0
n = int(input())
blue = [input() for i in range(n)]
m = int(input())
red = [input() for i in range(m)]
for i in range(m):
    if red[i] in blue:
        blue.remove(red[i])
for j in list(set(blue)):
    if blue.count(j) > ans:
        ans = blue.count(j)
print(ans)
A=int(input())
B=int(input())
K=int(input())

if A>K:
    A=A-K
    B=B
    print(A,B)
elif A<K:
    print(0,B-(K-A))

elif A<K and K-A>B:
    print(0,0)

### FIXED CODE ###

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

if A>=K:
    A=A-K
    B=B
    print(A,B)
elif A<K and K-A<B:
    print(0,B-(K-A))

elif A<K and K-A>B:
    print(0,0)
else:
    print(0,0)
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
c=0
mn=min(l)
while len(l)>=1:
  if mn==min(l):
    m=l.index(min(l))
    if m==0: # count == 0
      l=l[m+1:]
    elif m+l[k-1::-1].index(min(l))==len(l):
      c+=m//(k-1)
      if m%(k-1)!=0:
        c+=1
      l=l[m+1:]
    else: # count >= 2
      #print(l[k-1::-1])
      c+=1
      l=l[k:]
  else:
    c+=len(l)//(k-1)
    if len(l)%(k-1)!=0:
      c+=1
    l=[]
print(c)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
g=1
while k+(k-1)*(g-1)< n:
  g+=1
print(g)
n = int(input())
ans = []
while n != 0:
    o = chr(n%26 +96)
    ans.append(o)
    n //= 26
ans = reversed(ans)
print(''.join(ans))n = int(input())
ans = []
while n != 0:
    o = chr(n%26 +96)
    ans.append(o)
    n //= 26
ans = reversed(ans)
print(''.join(ans))

### FIXED CODE ###

n = int(input())
ans = []
keta = n//26
while n != 0:
    i = n%26
    if i == 0:
        o = 'z'
        n = n//26 -1
    else:
        o = chr(n%26 +96)
        n //= 26
    ans.append(o)
ans = reversed(ans)
print(''.join(ans))
S,T=map(input().split())
a,b=mao(int,input().split())
U=input()

if S==U:
  print(a-1,b)
else:
  print(a,b-1)

### FIXED CODE ###

S,T=input().split()
a,b=map(int,input().split())
U=input()

if S==U:
  print(a-1,b)
else:
  print(a,b-1)
n = int(input())
 
if n == 1:
  print("Hello World")
else:
  a,b = map(int, input().split())
  print(a+b)

### FIXED CODE ###

n = int(input())
 
if n == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(a+b)