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

import sys
N, M = map(int, sys.stdin.readline().split())
A = sorted(list(map(int, sys.stdin.readline().split())))
BC = [list(map(int,sys.stdin.readline().split())) for i in range(M)]
for i in range(len(BC)):
	BC[i] = BC[i][::-1]
BC = sorted(BC, reverse=True)
c = 0
for j in BC:
    for k in range(c, c + j[1]):
        if k < N:
            if A[k] < j[0]:
                A[k] = j[0]
    c = c + j[1]
print(sum(A))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
c = 0
I = 0
for i in CB:
    I += i[1]
    if flag:
        break
    while c < I:
        if c >= N:
            break
        if A[c] < i[0]:
            A[c] = i[0]
            c += 1
        else:
            c = I
            flag = True
print(sum(A))
### BUGGY CODE ###

param_x, param_k, param_d = map(int, input().split())

param_x_tmp = param_x

if param_x > 0:
  int_times_nega_posi = -1
else:
  int_times_nega_posi =  1

count = 0
while param_x_tmp*param_x > 0:
  
  param_x_tmp = param_x_tmp + param_d*int_times_nega_posi
  
  count = count + 1
  
  if param_k - count == 0:
    print(abs(param_x_tmp))

if count < param_k:
  int_move = param_k - count #move left
  int_move_devide_2_no_amari = int_move % 2
  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi*-1))

### FIXED CODE ###

param_x, param_k, param_d = map(int, input().split())

param_x_tmp = param_x

if param_x > 0:
  int_times_nega_posi = -1
else:
  int_times_nega_posi =  1
  
if (param_x*int_times_nega_posi*-1) - (param_k*param_d) > 0:
  print((param_x*int_times_nega_posi*-1) - (param_k*param_d))
  
else:
  int_time_before_cross_0 = int((param_x*int_times_nega_posi*-1) / param_d)
  # print(int_time_before_cross_0)
  
  param_x_tmp = param_x + int_time_before_cross_0*param_d*int_times_nega_posi
  # print(param_x_tmp)
  
  int_move = param_k - int_time_before_cross_0 #move left
  int_move_devide_2_no_amari = int_move % 2
  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi))
  
  #count = 0
  #while param_x_tmp*param_x > 0:
  #  
  #  param_x_tmp = param_x_tmp + param_d*int_times_nega_posi
  #  
  #  count = count + 1
  #  
  #  if param_k - count == 0:
  #    print(abs(param_x_tmp))
  #
  #if count < param_k:
  #  int_move = param_k - count #move left
  #  int_move_devide_2_no_amari = int_move % 2
  #  print(abs(param_x_tmp + param_d*int_move_devide_2_no_amari*int_times_nega_posi*-1))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
p=10**9 + 7 
l=[0]*60
for i in range(60):
    for j in a:
        l[i]+=(j>>i)&1
    ans=(ans + (2**i) * l[i] * (n-l[i]))%p
print(ans) 

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
p=10**9 + 7 
l=[0]*60
for i in range(60):
    for j in a:
        l[i]+=(j>>i)&1
    ans=(ans + (2**i) * l[i] * (n-l[i]))%p
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
N=[0]*2020
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    x%=2019
    N[x]+=1
ans=s.count('0')
ans+=N[0]
for j in N:
    ans+=j*(j-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*pow(10,(n-i-1),2019)
    x%=2019
    N[x]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)
### BUGGY CODE ###

from sys import stdin
def main():
    n = int(stdin.readline().rstrip())
    a = list(map(int,stdin.readline().rstrip().split()))
    mod = 10**9+7
    point = 0
    kai = [2**i%mod for i in range(61)]
    for i in range(61):
        now = (sum(1 for j in a if(j >> i)&1))
        now *= (n-now)*kai[i]
        now %= mod
        point += now
    print(point%mod)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
point = 0
for i in range(61):
    now = 0
    for j in a:
        now += (j >> i&1)
    now *= n-now
    now %= mod
    for k in range(i):
        now *= 2
        now %= mod
    point += now
    point %= mod
print(point)
### BUGGY CODE ###

import numpy as np

n = int(input())
A = np.asarray(list(map(int, input().split())))
B = np.asarray(list(map(int, input().split())))
AB = np.dstack((A, B))[0]
AB = AB[np.argsort(AB[:, 1])]

flag = False
k = 0
while(not flag and k<n):
    if AB[k,0] <= AB[k,1]:
        ABd = np.delete(AB, k, 0)

        As = ABd[:, 0]

        As.sort()

        for i in range(n-1):
            if As[i] > ABd[i, 1]:
                break
        else:
            flag = True

    k += 1

if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n = int(input())
lsa = list(map(int, input().split()))
lsb = list(map(int, input().split()))

ls = [[a, b] for a, b in zip(lsa, lsb)]
ls.sort(key=lambda x: x[1])
lsa = [l[0] for l in ls]
lsb = [l[1] for l in ls]

lsasort = sorted(lsa)
for i in range(n):
    if lsasort[i]>lsb[i]:
        flag = False
        break
else:
    flag = True

if flag:
    lscycle = [[p, q] for p, q in zip(range(n), lsa)]
    lscycle.sort(key=lambda x: x[1])

    count=0
    idx=0
    while True:
        idx=lscycle[idx][0]
        count+=1
        if idx == 0:
            break

    if count != n:
        flag = True
    else:
        for i in range(n-1):
            if lsasort[i+1] <= lsb[i]:
                flag = True
                break
        else:
            flag = False

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np


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

bom_cord = np.empty((m, 2), dtype=int)
h_cnt = np.zeros(h, dtype=int)
w_cnt = np.zeros(w, dtype=int)
bom_cord = set()
for i in range(m):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    bom_cord.add((hi, wi))
    h_cnt[hi] += 1
    w_cnt[wi] += 1

w_max = w_cnt.max()

h_argsort = h_cnt.argsort()[::-1]
w_argsort = w_cnt.argsort()[::-1]

bomber = 0
for hi in h_argsort:
    if h_cnt[hi] + w_max < bomber:
        break
    
    for wi in w_argsort:
        if h_cnt[hi] + w_cnt[wi] < bomber:
            break

        if (hi, wi) in bom_cord:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi] - 1)
        else:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi])

print(bomber)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np


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

h_cnt = np.zeros(h, dtype=int)
w_cnt = np.zeros(w, dtype=int)
bom_cord = set()
for i in range(m):
    hi, wi = map(lambda x: int(x) - 1, input().split())
    bom_cord.add((hi, wi))
    h_cnt[hi] += 1
    w_cnt[wi] += 1

w_max = w_cnt.max()

h_argsort = h_cnt.argsort()[::-1]
w_argsort = w_cnt.argsort()[::-1]

bomber = 0
for hi in h_argsort:
    if h_cnt[hi] + w_max <= bomber:
        break
    
    for wi in w_argsort:
        if h_cnt[hi] + w_cnt[wi] <= bomber:
            break

        if (hi, wi) in bom_cord:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi] - 1)
        else:
            bomber = max(bomber, h_cnt[hi] + w_cnt[wi])

print(bomber)
### BUGGY CODE ###

import math
N, P = map(int, input().split())
ProotN = pow(P, 1/N)
# print(ProotN)
for i in range(math.ceil(ProotN), 0, -1):
    if (P/i**N).is_integer():
        print(i)
        break

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    dic = {}
    while i * i <= n:
        while n % i == 0:
            n /= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    if n > 1:
        dic[int(n)] = 1
    return dic

N, P = map(int, input().split())
d = prime_decomposition(P)
ret = 1
for k, v in d.items():
    if v >= N:
        ret *= k ** (v//N)
print(ret)
### BUGGY CODE ###

def main():
    A, B, C, D = map(int, input().split())

    while True:
        Aoki_health = C-B
        Take_health = A-D
        if Take_health <= 0 < Aoki_health:
            print('No')
            break
        if Aoki_health <= 0 < Take_health: 
            print('Yes')
            break


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def main():
    A, B, C, D = map(int, input().split())

    Takeshi = math.ceil(C/B)
    Aoki = math.ceil(A/D)

    print('Yes' if Takeshi<= Aoki else 'No')


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

import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = np.argmin(np.abs(a - t))
    b_dis = np.argmin(np.abs(b - t))
    print(np.min([np.abs(b[b_dis] - t) + np.min(np.abs(a[np.max([a_dis-1,0]):a_dis+1] - b[b_dis])), np.abs(a[a_dis] - t) + np.min(np.abs(b[np.max([b_dis-1,0]):b_dis+1] - a[a_dis]))]))

### FIXED CODE ###

import bisect
import numpy as np
 
hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

def search_min_pos(arr, target):
  index = bisect.bisect_left(arr, target)
  if 0 == index:
    dist = arr[index]
  else:
    dist = arr[index-1:index+1]
  if not isinstance(dist, list):
    dist = [dist]
  return dist

a_arr = s[:hint[0]]
b_arr = s[hint[0]:-hint[2]]
sum = 0
for t in s[-hint[2]:]:
  a_pos = search_min_pos(a_arr, t)
  b_pos = search_min_pos(b_arr, t)
  #print(t, a_pos, b_pos)
  min_dist = 10 ** 11
  for a in a_pos:
    b_against_a = search_min_pos(b_arr, a)
    for ba in b_against_a:
      min_dist = min([min_dist, abs(t-a)+abs(ba-a)])
  for b in b_pos:
    a_against_b = search_min_pos(a_arr, b)
    for ab in a_against_b:
      min_dist = min([min_dist, abs(t-b)+abs(ab-b)])
  print(min_dist)
### BUGGY CODE ###

from itertools import islice

def make_gen():
    n, m, l = list(map(int, input().split()))

    m1 = [list(map(int, input().split())) for _ in range(n)]
    m2 = [list(map(int, input().split())) for _ in range(m)]

    def g():
        for r1 in m1:
            for r2 in zip(*m2):
                yield str(sum(i*j for i, j in zip(r1, r2)))

    return (n, l, g)

n, l, g = make_gen()
for i in range(n):
    print(" ".join(islice(g(), i*l, (i+1)*l)))

### FIXED CODE ###

from itertools import islice

def make_seq():
    n, m, l = list(map(int, input().split()))

    m1 = [list(map(int, input().split())) for _ in range(n)]
    m2 = [list(map(int, input().split())) for _ in range(m)]

    def g():
        for r1 in m1:
            for r2 in zip(*m2):
                yield str(sum(i*j for i, j in zip(r1, r2)))

    return (n, l, list(g()))

n, l, lst = make_seq()
for i in range(n):
    print(" ".join(islice(lst, i*l, (i+1)*l)))
### BUGGY CODE ###

import numpy as np
n, k, q = map(int, input().split())
l = [int(input()) for i in range(q)]
ls = np.array([k]*n)
for i in l:
    ls[:i-1] -= 1
    ls[i:] -= 1
for i in range(n):
    if ls[i]>0:
        print('Yes')
    else :
        print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
s = [k]*n
for i in range(q):
    a = int(input())
    s[a-1] += 1
for key in s:
    if key-(q) > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

answer = 1
for a in A:
  answer = answer*a

if answer > 10**18:
  answer = -1
  
print(answer)

### FIXED CODE ###

import sys

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

answer = 1

for a in A:
  if a == 0:
    answer = 0
    print(answer)
    sys.exit()
    
for a in A:
  answer = answer*a
  if answer > 10**18:
    answer = -1
    print(answer)
    sys.exit()


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

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

for i in range(1, n, 2):
    if a_list.count(n - i) != 2:
        print(0)
        exit()

if n % 2 != 0:
    if a_list.count(0) != 1:
        print(0)
        exit()
    else:
        print((2 ** -(-(len(a_list) - 1) // 2)) % (1000000000 + 7))
else:
    print((2 ** (len(a_list) // 2)) % (1000000000 + 7))


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
### BUGGY CODE ###

from collections import defaultdict, deque

inf = float('inf')

H, W = map(int, input().split())
d = defaultdict(bool)  # False

dq = deque()
for r in range(H):
    a = input()
    for c in range(W):
        if a[c] == '#':
            d[(r, c)] = 0
            dq.append((r, c, 0))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


while dq:
    r, c, dist = dq.popleft()
    if not d[(r + 1, c)] and in_range(r + 1, c):
        d[(r + 1, c)] = dist + 1
        dq.append((r + 1, c, dist + 1))
    if not d[(r - 1, c)] and in_range(r - 1, c):
        d[(r - 1, c)] = dist + 1
        dq.append((r - 1, c, dist + 1))
    if not d[(r, c + 1)] and in_range(r, c + 1):
        d[(r, c + 1)] = dist + 1
        dq.append((r, c + 1, dist + 1))
    if not d[(r, c - 1)] and in_range(r, c - 1):
        d[(r, c - 1)] = dist + 1
        dq.append((r, c - 1, dist + 1))

# print(d)
print(dist)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(H)]
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r][c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)
### BUGGY CODE ###

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

c = 0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        c += 1
print(c)

### FIXED CODE ###

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

c = 0

for x in range(k+1):
  for y in range(k+1):
    if 0 <= (s - x - y) <= k:
      c += 1
print(c)
### BUGGY CODE ###

S = input()
c = 0
while 'BW' in S:
  c += S.count('BW')
  S = S.replace('BW', 'WB')
print(c)

### FIXED CODE ###

S = input()
x = len(S)
c = 0
ans = 0
for i in range(x):
  
  if S[i] == 'W':
    
    c += 1
    
    ans += i + 1 - c
    
    
print(ans)
### BUGGY CODE ###

import numpy 
from fractions import gcd

mod = 10**9+7

n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d = d * a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
  ans %= mod

print(ans)

### FIXED CODE ###

from sys import stdin
input = stdin.readline
from fractions import gcd
 
mod = 10**9+7
 
n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d *= a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
 
print(ans%mod)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
l=[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]
a=0
K=int(input())
for i in range(1,K+1):
    if i in l:
        a+=K**2 +(i-1)*(K//i)**2
    else:
        for j in range(1,K+1):
            if j in l:
                if math.gcd(i,j)==1:
                    a+=K
                else:
                    a+=(K + (math.gcd(i,j)-1)*(K//j))
            else:
                for r in range(1,K+1):
                    a+=gcd(i,j,r)
print(a)

### FIXED CODE ###

import math

a=0

K=int(input())
for i in range(1,K+1):#(1,2,3)
    for j in range(i,K+1):
        for r in range(j,K+1):
            if i==j and i==r:#(1,1,1)のような場合
                a+=math.gcd(i,math.gcd(j,r))
            elif i==j or j==r:#(1,1,2),(1,2,2)のような場合。各3通り
                a+=math.gcd(i,math.gcd(j,r))*3
            else:
                a+=math.gcd(i,math.gcd(j,r))*6
print(a)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	h,w=map(int,input().split())
	AB=np.array(read().split(), np.int64)
	
	
	A=AB[:h*w]
	B=AB[h*w:]
	
	A=np.reshape(A, (h,w))
	B = np.reshape(B, (h, w))
	
	G=abs(A-B)
	M=h*w*80
	
	li=[[[]for i in range(w)] for j in range(h)]
	for i in range(h):
		for j in range(w):
			if i==j==0:
				li[i][j].append(G[i][j])
			elif i==0:
				for k in li[i][j-1]:
					aa=abs(k-G[i][j])
					bb=abs(k+G[i][j])
					if aa<=M:
						li[i][j].append(aa)
					if abs(bb)<=M:
						li[i][j].append(bb)
			elif j==0:
				for k in li[i-1][j]:
					aa=abs(k-G[i][j])
					bb=abs(k+G[i][j])
					if aa<=M:
						li[i][j].append(aa)
					if abs(bb)<=M:
						li[i][j].append(bb)
			else:
				for k in li[i-1][j]:
					aa=abs(k-G[i][j])
					bb=abs(k+G[i][j])
					if aa<=M:
						li[i][j].append(aa)
					if abs(bb)<=M:
						li[i][j].append(bb)
				for k in li[i][j-1]:
					aa=abs(k-G[i][j])
					bb=abs(k+G[i][j])
					if aa<=M:
						li[i][j].append(aa)
					if abs(bb)<=M:
						li[i][j].append(bb)
			
			s=set(li[i][j])
			li[i][j]=list(s)
			
			
			
			
	print(min(li[h-1][w-1]))
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	h, w = map(int, input().split())
	
	G = [[0] * w for i in range(h)]
	A = [0]*h
	B = [0]*h
	
	for i in range(h):
		A[i] = list(map(int, input().split()))
	for i in range(h):
		B[i] = list(map(int, input().split()))
	
	for i in range(h):
		for j in range(w):
			G[i][j]=abs(A[i][j]-B[i][j])

	M = (h + w) * 80

	li = [[[0] * M for i in range(w)] for j in range(h)]
	
	li[0][0][G[0][0]] = 1
	for i in range(h):
		for j in range(w):
			for k in range(M):
				
				if li[i][j][k] == 1:
					if i < h - 1:
						li[i + 1][j][abs(k - G[i+1][j])] = 1
						li[i + 1][j][abs(k + G[i+1][j])] = 1
					if j < w - 1:
						li[i][j + 1][abs(k - G[i][j+1])] = 1
						li[i][j + 1][abs(k + G[i][j+1])] = 1

	for i in range(M):
		if li[h-1][w - 1][i] == 1:
			print(i)
			exit(0)


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

from collections import Counter

n = int(input())
aL = [set(Counter(input()).most_common()) for i in range(n)]
count = 0

for i in range(n):
    for j in range(n):
        if i<j:
            if aL[i] == aL[j]:
                count +=1

print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
counter = Counter()
ans = 0
for s in S:
    a = ''.join(sorted(list(s)))
    if a in counter:
        ans += counter[a]
    counter[a] += 1
print(ans)
### BUGGY CODE ###

n=int(input())
a = [input() for _ in range(n)]
c=[0]*n

for i in range(n):
	b=a.copy()
	b.remove(a[i])
	c[i]=sorted(b)[-1]
for i in range(n):
	print(c[i])

### FIXED CODE ###

n=int(input())
a = [int(input()) for _ in range(n)]
b=sorted(a)
c=[0]*n

for i in range(n):
	if a[i]==b[-1]:
		c[i]=b[-2]
	else:
		c[i]=b[-1]
for i in range(n):
	print(c[i])
### BUGGY CODE ###

import re

def checkFunction(c):
    c = re.sub('W+$','',c)
    if (not 'WR' in c):
        return 0
    if c.index('WR') + 2 != len(c):
        c2 = c.replace('WR', 'RR',1)[:-1]
        return checkFunction(c2) + 1
    return 1

N = int(input())
c= input()

print(checkFunction(c))

### FIXED CODE ###


def check(N, c):
    RinRight = c.count('R')
    WinLeft = 0
    r = RinRight
    for i in range(N):
        if c[i] == 'R':
            RinRight -= 1
        else: # c[i] == 'W'
            WinLeft +=1
        r = min(r, max(RinRight,WinLeft))

    return r


N = int(input())
c= input()
print(check(N,c))
### BUGGY CODE ###

#!/usr/bin/env python3
import copy

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

pcnt = 0
mcnt = 0

f = 0  #前の項の符号（1:+、2:-）
wa = 0

#最初の数字を正とするとき
a = copy.copy(am)
f = 2

for i in range(len(a)):
    wa += a[i]

    if f == 1:#-にする必要あり
        if wa > -1:
            pcnt += wa + 1
            a[i] -= wa + 1

        f = 2

    elif f == 2:  #+にする必要あり

        if wa < 1:
            pcnt += -wa + 1
            a[i] += -wa + 1
        
        f = 1
    
    wa = sum(a[0: i + 1])

#最初の数字を負とするとき
a = copy.copy(am)
f = 1

for i in range(len(a)):
    wa += a[i]

    if f == 1:  # -にする必要あり
        if wa > -1:
            mcnt += wa + 1
            a[i] -= wa + 1

        f = 2

    elif f == 2:  # +にする必要あり

        if wa < 1:
            mcnt += -wa + 1
            a[i] += -wa + 1

        f = 1

    wa = sum(a[0: i + 1])

print(min(pcnt, mcnt))


### FIXED CODE ###

#!/usr/bin/env python3
import copy

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

pcnt = 0
mcnt = 0

f = 0  #前の項の符号（1:+、2:-）
wa = 0

#最初の数字を正とするとき
a = copy.copy(am)
f = 2

for i in range(n):
    wa += a[i]

    if f == 1:#-にする必要あり
        if wa > -1:
            pcnt += wa + 1
            wa = -1
        
        f = 2

    elif f == 2:  #+にする必要あり

        if wa < 1:
            pcnt += -wa + 1
            wa = 1

        f = 1

#最初の数字を負とするとき
a = copy.copy(am)
wa = 0
f = 1

for i in range(n):
    wa += a[i]

    if f == 1:  # -にする必要あり
        if wa > -1:
            mcnt += wa + 1
            wa = -1

        f = 2

    elif f == 2:  # +にする必要あり

        if wa < 1:
            mcnt += -wa + 1
            wa = 1

        f = 1

print(min(pcnt, mcnt))
### BUGGY CODE ###

s=raw_input()
q=int(raw_input())

for i in range(0, q):
    t=raw_input()
    if t[0] == "1":
        s = s[::-1]
    else:
        if t[2] == "1":
            s = t[4] + s
        else:
            s = s + t[4]

print s


### FIXED CODE ###

from collections import deque
#s=raw_input()

l=deque(list(input()))
q=int(input())

r=False
for i in range(0, q):
    t=input()
    if t[0] == "1":
        r = not r
        #s = s[::-1]
    else:
        if t[2] == "1" and r is False or t[2] == "2" and r is True:
            #s = t[4] + s
            l.appendleft(t[4])
        else:
            #s = s + t[4]
            l.append(t[4])

if r is True:
    #s = s[::-1]
    l = list(l)[::-1]

#print s
print("".join(l))
### BUGGY CODE ###

s=input()
t=input()
ma=0
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
pred=[[-1 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        dp[i][j]=max(dp[i][j],dp[i-1][j])
        dp[i][j]=max(dp[i][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])
        if dp[i][j]==1+dp[i-1][j-1]:
            pred[i][j]=[i-1,j-1]
        if dp[i][j]==dp[i][j-1]:
            pred[i][j]=[i,j-1]
        if dp[i][j]==dp[i-1][j]:
            pred[i][j]=[i-1,j]
            

        ma=max(ma,dp[i][j])
ans=""
a=[-1,-1]
ma=-1
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if dp[i][j]>ma:
            ma=dp[i][j]
            a=[i,j][:]
b=a[:]
ans=[b[:]]
while b!=-1:
    #print(b)
    b=pred[b[0]][b[1]][:]
    if 0 in b:
        break
    if b!=-1:
        ans.append(b)


ss=""
for  i in ans:
    if s[i[0]-1]==t[i[1]-1]:
        ss+=s[i[0]-1]
ss=ss[-1::-1]
print(ss)
    


### FIXED CODE ###

s=input()
t=input()
ma=0
a=[0,0]
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])
i=len(s)
j=len(t)

ss=""
while i and j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ss+=s[i-1]
        i-=1
        j-=1
ss=ss[-1::-1]
print(ss)