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

import sys

# sys.stdin = open('d1.in')

n, m = map(int, input().split())
weights = {}
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    weights[(a, b)] = c

score = [-10 ** 50] * n
score[0] = 0
pred = [-1] * n
for i in range(n):
    for edge, c in weights.items():
        a, b = edge
        if score[b] < score[a] + c:
            score[b] = score[a] + c
            pred[b] = a
res = score[n - 1]

b = n - 1
while b != 0:
    a = pred[b]
    c = weights[(a, b)]
    if score[b] < score[a] + c:
        res = 'inf'
    b = a

print(res)


### FIXED CODE ###

import sys

# sys.stdin = open('d1.in')

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges.append((a, b, c))

score = [-10 ** 50] * n
score[0] = 0
for i in range(n):
    for a, b, c in edges:
        if score[b] < score[a] + c:
            score[b] = score[a] + c
res = score[n - 1]

for i in range(n):
    for a, b, c in edges:
        if score[b] < score[a] + c:
            score[b] = score[a] + c
if res < score[n - 1]:
    res = 'inf'
print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
M = {}
K = int(input())
for i in range(K):
    V, P = map(int, input().split())
    M[V-1] = P
memo = [0]*N
def dfs(v, p, x, y):
    if v in M:
        x = y = M[v]
    x0 = x; y0 = y
    for w in G[v]:
        if p == w:
            continue
        s, t = dfs(w, v, x-1, y+1)
        x0 = max(x0, s-1)
        y0 = min(y0, t+1)
    for w in G[v]:
        if p == w:
            continue
        dfs(w, v, x0-1, y0+1)
    memo[v] = x0, y0
    return x0, y0
INF = 10**18
dfs(list(M.keys())[0], -1, -INF, INF)
ok = 1
for i in range(N):
    x, y = memo[i]
    if not x <= y:
        ok = 0
if ok:
    print('Yes')
    print(*map(lambda x: x[1], memo), sep='\n')
else:
    print('No')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
M = {}
K = int(input())
for i in range(K):
    V, P = map(int, input().split())
    M[V-1] = P
memo = [0]*N
def dfs(v, p, x, y):
    if v in M:
        x = y = M[v]
    x0 = x; y0 = y
    for w in G[v]:
        if p == w:
            continue
        s, t = dfs(w, v, x-1, y+1)
        x0 = max(x0, s-1); y0 = min(y0, t+1)
    memo[v] = x0, y0
    return x0, y0
def dfs1(v, p, x, y, c):
    if v in M:
        x = y = M[v]
        if c != (M[v] % 2):
            return 0
    x0, y0 = memo[v]
    x = max(x, x0); y = min(y, y0)
    for w in G[v]:
        if p == w:
            continue
        if not dfs1(w, v, x-1, y+1, c^1):
            return 0
    memo[v] = x, y
    return 1

INF = 10**18
f = list(M.keys())[0]
dfs(f, -1, -INF, INF)
ok = dfs1(f, -1, -INF, INF, M[f]%2)
for i in range(N):
    x, y = memo[i]
    if not x <= y:
        ok = 0
if ok:
    print('Yes')
    print(*map(lambda x: x[1], memo), sep='\n')
else:
    print('No')
### BUGGY CODE ###

import sys
import bisect
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    b = list(map(int, readline().split()))
    dp = [0] * 31
    for i in range(28, -1, -1):
        mdr = pow(2, i + 1)
        mdl = pow(2, i)
        for j in range(n-1, -1, -1):
            b[j] %= mdr
            a[j] %= mdr
        a.sort(reverse=True)
        b.sort()
        p_mdr_av = 0
        p_mdl_av = 0
        p_mdr = 0
        p_mdl_mdr_av = 0
        d = collections.defaultdict(int)
        for av in a:
            if mdl - av >= 0:
                p_mdr_av = bisect.bisect_left(b, mdr - av, p_mdr_av)
                p_mdl_av = bisect.bisect_left(b, mdl - av, p_mdl_av, p_mdr_av)
                dp[i] += p_mdr_av - p_mdl_av
            else:
                p_mdr = bisect.bisect_left(b, mdr, p_mdr)
                p_mdr_av = bisect.bisect_left(b, mdr - av, p_mdr_av, p_mdr)
                dp[i] += p_mdr_av
                p_mdl_mdr_av = bisect.bisect_left(b, mdl + mdr - av, p_mdl_mdr_av)
                dp[i] += p_mdr - p_mdl_mdr_av
    t = 0
    for i in range(31):
        t += pow(2, i) * (dp[i] % 2)
    print(t)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import bisect

readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))


def f(md):
    pos = n - 1
    res = 0
    for av in a:
        while True:
            if pos != -1 and av + b[pos] >= md:
                pos -= 1
            else:
                res += pos + 1
                break
    return res


def solve():
    dp = [0] * 31
    for i in range(28, -1, -1):
        md = pow(2, i + 1)
        for j in range(n-1, -1, -1):
            b[j] %= md
            a[j] %= md
        a.sort()
        b.sort()
        res1, res2, res3 = f(md // 2), f(md // 2 * 2), f(md // 2 * 3)
        dp[i] += (n - (res1 + res3 - res2)) % 2
    t = 0
    for i in range(31):
        t += pow(2, i) * (dp[i] % 2)
    print(t)


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

s = input()
q = int(input())

cnt_reverse = False
for i in range(q):
  query = input()
  
  if query[0] == '1':
    cnt_reverse = not cnt_reverse
  elif (query[2] == '1' and not cnt_reverse) or (query[2] == '2' and cnt_reverse):
    s = query[4] + s
  else:
    s  = s + query[4]
if cnt_reverse:
  s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())

cnt_reverse = False
left = ''
for i in range(q):
  query = input()
  
  if query[0] == '1':
    cnt_reverse = not cnt_reverse
  elif (query[2] == '1' and not cnt_reverse) or (query[2] == '2' and cnt_reverse):
    left = left + query[4]

  else:
    s  = s + query[4]
s = left[::-1] + s
if cnt_reverse:
  s = s[::-1]
print(s)
### BUGGY CODE ###

N = int(input())
 
N_1 = N - 1
counts = 0
i = 1
j = 1
while i <= N_1:
    while j <= N_1:
        if i * j <=  N_1:
            counts = counts + 1
        else:
            j = N_1
        j = j + 1
    j = 1
    i = i + 1
 
print(counts)

### FIXED CODE ###

N = int(input())

N_1 = N - 1
counts = 0
i = 1
j = 1
while i <= N_1:
    while j <= N_1:
        if i * j <=  N_1:
            counts = counts + 1
        else:
            j = N_1
        j = j + 1
    j = 1
    i = i + 1

print(counts)
### BUGGY CODE ###

A, B, C, X, Y = map(int, input().split())

min_cost = 1e10
for a in range(X+1):
    for b in range(Y+1):
        left = max(X-a, Y-b)
        cost = a*A + b*B + left*C*2
        if cost < min_cost:
            min_cost = cost
print(min_cost)

### FIXED CODE ###

A, B, C, X, Y = map(int, input().split())

min_cost = 1e10
for a in range(X+1):
    c = (X-a)*2
    left_b = max(0, Y - (X-a))
    cost = a*A+round(left_b)*B+c*C
    if cost < min_cost:
        min_cost = cost
    # 残り全部をABピザで賄う場合
    left_b = max(X-a, Y)
    cost = a*A + left_b*2*C
    if cost < min_cost:
        min_cost = cost
print(min_cost)
### BUGGY CODE ###

import itertools

K, S = map(int, input().split())
num = list(range(K+1))
count = 0

for x in range(K+1):
    if K < 1/2 * (S - x):
        continue
    for y in range(min(S - x + 1, K + 1)):
        if K < (S - x - y):
            continue
        for z in range(min(S - x - y + 1, K + 1)):
            if x + y + z == S:
                count +=1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    if K < 1/2 * (S - x):
        continue
    for y in range(min(S - x + 1, K + 1)):
        if K < (S - x - y):
            continue
        else:
            count += 1
print(count)
### BUGGY CODE ###

s = list(input())
n=int(input())
l = [input().split(" ") for _ in range(n)]

for i in range(n):
    if l[i][0]=='1':
        s=s[::-1]
    elif l[i][0]=='2':
        if l[i][1]=='1':
            s = [l[i][2]]+s
        else:
            s.append(l[i][2])
print(''.join(s))


### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())
l = [input().split(" ") for _ in range(n)]

x = 0
for i in range(n):
    if l[i][0]=='1':
        if x == 0:
            x = 1
        else:
            x = 0
    elif l[i][0]=='2':
        if x == 0:
            if l[i][1]=='1':
                s.appendleft(l[i][2])
            else:
                s.append(l[i][2])
        else:
            if l[i][1]=='1':
                s.append(l[i][2])
            else:
                s.appendleft(l[i][2])

if x == 0:
    print(''.join(s))
else:
    print(''.join(reversed(s)))
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()
for _ in range(q):
    l,r=map(int,input().split())
    print(len(re.findall('AC',s[l-1:r],re.S)))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]
total=0
for i in range(1,len(s)):
    if s[i]=='C':
        if s[i-1]=='A':
            total+=1
    a.append(total)
a.append(total)

for _ in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

n = int(input())
nn = 0

if n >= 357:
    for i in range(357,n+1):
        s = str(i)
        if ('0' in s or '1' in s or '2' in s or '4' in s or '6' in s or '8' in s or '9' in s) is False:
            if '3' in s and '5' in s and '7' in s:
                #print(i)
                nn += 1
print(nn)

### FIXED CODE ###

def nextn(n):
    if n == 0:
        return 3
    elif n % 10 == 3:
        return n+2
    elif n % 10== 5:
        return n+2
    elif n % 10 ==7:
        return nextn(n//10)*10 + 3

N = int(input())
n = 357
ans = 0
while n <= N:
    s = str(n)
    a = [False,False,False]
    for c in s:
        if c == '3':
            a[0] = True
        elif c == '5':
            a[1] = True
        elif c == '7':
            a[2] = True
        else:
            print(s)
    if all(a):
        ans += 1
    n = nextn(n) 
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
l1 = copy.deepcopy(l)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if l[i][j] > l[i][k]+l[k][j]:
                print(-1)
                exit()

            elif l[i][j] == l[i][k]+l[k][j]:
                if i != k and k != j :
                    l1[i][j] = 0
ans = 0
for i in l1:
    for j in i:
        ans += j
print(ans//2)


### FIXED CODE ###

import copy
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
l1 = copy.deepcopy(l)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if l[i][j] > l[i][k]+l[k][j]:
                print(-1)
                exit()

            elif l[i][j] == l[i][k]+l[k][j]:
                if i != k and k != j :
                    l1[i][j] = 0
ans = 0
for i in l1:
    for j in i:
        ans += j
print(ans//2)
### BUGGY CODE ###

def factorize(a):
    x=2
    ret=[]
    while x<=a:
        while a%x==0:
            a//=x
            ret.append(x)
        x+=1
    return ret
a,b=map(int,input().split())
set_fac_a=set(factorize(a))
set_fac_b=set(factorize(b))
set_ans=set_fac_a & set_fac_b
print(len(set_ans)+1)

### FIXED CODE ###

def factorize(a):
    x=2
    ret=[]
    rt_a=a**0.5
    while x<=a:
        if(x>=rt_a):
            ret.append(a)
            break
        if(a%x==0):
            ret.append(x)
        while a%x==0:
            a//=x
        x+=1
    return ret

def gcd(a,b):
    tmp=a
    a=max(a,b)
    b=min(tmp,b)
    if(a%b==0):
        return b
    return gcd(b,a%b)

a,b=map(int,input().split())
print(len(set(factorize(gcd(a,b))))+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
import numpy

S = input()
length=len(S)
dp = numpy.zeros(26)
dp[0]=1
for i in range(length-1):
    for j in range(13):
        if S[length-i-2] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[j+13]+=dp[j_sub]%1000000007
        else: 
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[j+13]+=dp[j_sub]%1000000007
    dp[0:13] = dp[13:]
    dp[13:]=0
#print(int(dp%1000000007))
print(int(dp[5]%1000000007))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import bisect
import sys
input=sys.stdin.readline
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
ans='NO'
d.sort()
for i in range(m):
    cnt=bisect.bisect_right(d,t[i])-1
    if d[cnt]==t[i]:
        d.pop(cnt)
        if i==m-1:
            ans='YES'
    else:
        break
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))

d_c=Counter(d)
t_c=Counter(t)
for i in t_c.keys():
    if t_c[i]>d_c[i]:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

def main():
    S=input()
    P=2019
    ans=0
    
    count=[0]*P
    count[0]=1
    u=0
    
    for i,s in enumerate(reversed(S)):
        u=(int(s)*pow(10,i)%P+u)%P
        ans+=count[u]
        count[u]+=1
    print(ans)
    

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    S=input()
    P=2019
    ans=0
    
    count=[0]*P
    count[0]=1
    u=0
    
    for i,s in enumerate(reversed(S)):
        u=(int(s)*pow(10,i,P)+u)%P
        ans+=count[u]
        count[u]+=1
    print(ans)
    

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

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

def bfs(y, x):
    cnt = [[-1] * w for _ in range(h)]
    queue = deque([[y, x]])
    cnt[y][x] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                if s[i + di][j + dj] == ".":
                    cnt[i][j] += 1
                    queue.append([i + di, j + dj])
                else:
                    return cnt[i][j]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[-1] * w for _ in range(h)]

def bfs():
    queue = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                queue.append([i, j])
                cnt[i][j] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                queue.append([i + di, j + dj])
                cnt[i + di][j + dj] = cnt[i][j] + 1

bfs()
print(max([max(l) for l in cnt]))
### BUGGY CODE ###

import re
if __name__ == '__main__':
    S = str(input())
while True:
    S_new = re.sub(r'eraser$|erase$|dreamer$|dream$', '', S)
    if S_new == S:
        print('NO')
        break
    elif S_new == '':
        print('YES')
        break
    S = S_new

### FIXED CODE ###

if __name__ == '__main__':
    S = str(input())
    T = ''
    while True:
        if len(S) == 0:
            print('YES')
            break
        elif S[len(S)-7:len(S)] == 'dreamer':
            S = S[:len(S)-7]
            continue
        elif S[len(S)-6:len(S)] == 'eraser':
            S = S[:len(S)-6]
            continue
        elif S[len(S)-5:len(S)] == 'dream':
            S = S[:len(S)-5]
            continue
        elif S[len(S)-5:len(S)] == 'erase':
            S = S[:len(S)-5]
            continue
        else:
            print('NO')
            break
### BUGGY CODE ###

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

while n>0:
    n -= k

n = abs(n)

print(min(n, abs(n-k)))

### FIXED CODE ###

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

n %= k

n = abs(n)

print(min(n, abs(n-k)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    X, Y = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7


    dp = [[0 for i in range(X + 1)] for j in range(Y + 1)]
    dp[0][0] = 1

    for i in range(X + 1):
        for j in range(Y + 1):
            x = j - 1
            y = i - 2
            if x >= 0 and y >= 0:
                dp[j][i] += dp[x][y]
            x = j - 2
            y = i - 1
            if x >= 0 and y >= 0:
                dp[j][i] += dp[x][y]

    print(dp[Y][X] % MOD)







if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

def modPow(a, x, p):
    res = 1
    while x > 0:
        if x % 2 != 0:
            res = res * a % p
        a = a * a % p
        x = x // 2
    return res

def modInverse(a, p):
    return modPow(a, p - 2, p)

def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    X, Y = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7
    y = (X - 2 * Y) // (-3)
    x = (X - y) // 2

    if y < 0 or x < 0:
        print(0)
        exit()
    if X == x * 2 + y and Y == x + 2 * y:
        print(modBinomial(x + y, x, MOD))
    else:
        print(0)









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

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

# 0 0
# 1 0
# 2 1
# 3 3
# 4 6

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

data = collections.Counter(A)
dict = {}

for i in range(N):
    if dict.get(A[i]) == None :
        ans = 0
        tmp = copy.copy(data)
        tmp[A[i]] = data[A[i]] - 1
        C = list(tmp.values())
        for j in range(len(C)):
            if C[j] >= 2:
                ans += comb(C[j],2)
        dict[A[i]] = ans
    else:
        ans = dict.get(A[i])
    print(ans)

### FIXED CODE ###

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]


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

C = [0]*(2*10**5+1)

for i in A:
    C[i] += 1

ans = sum(i*(i-1)//2 for i in C)

for i in A:
    print(ans-C[i]+1)
### BUGGY CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
edge = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

cnt = {}
for i in range(1, N+1):
    cnt[i] = 0
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

root_id = 1
open_list = [root_id]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    closed_list.append(cur_id)
    adj_id_list = edge[cur_id]
    for adj_id in adj_id_list:
        if adj_id in closed_list:
            continue
        cnt[adj_id]+=cnt[cur_id]
        open_list.append(adj_id)
print(*cnt.values())

### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
edge = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

cnt = [0]*(N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

root_node = (1, -1) # (id, value, parent_id)
open_list = [root_node]
closed_list = []
while True:
    if len(open_list) == 0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    if not(parent_id == -1):
        cnt[cur_id] += cnt[parent_id]
    for child_id in edge[cur_id]:
        if child_id == parent_id:
            continue
        open_list.append((child_id, cur_id))
print(*cnt[1:])
### BUGGY CODE ###

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

def main():
    s = input().split(" ")

    sl = list(s[0])
    prev = -1
    n = 0
    while True:
        # print(str(sl))
        if len(sl) < 1:
            break
        kita = False
        for i, c in enumerate(sl):
            if i == 0 and prev != -1:
                break
            if (prev == 0 and c == '1') or (prev == 1 and c == '0'):
                kita = True
                # print("remove", i, prev, c)
                del sl[i]
                del sl[i-1]
                n += 2
                prev = -1
                break
            else:
                kita = True
                prev = int(c)

        if not kita:
            break

    print(n)

main()


### FIXED CODE ###

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

def main():
    s = input().split(" ")

    sl = list(s[0])
    prev = -1
    n = 0

    i = 0
    while True:
        if len(sl) <= i:
            break

        if (prev == 0 and sl[i] == '1') or (prev == 1 and sl[i] == '0'):
            # print(str(sl))
            # print("remove", i, prev, sl[i])
            del sl[i]
            del sl[i-1]
            n += 2
            if i-2 < 0:
                prev = -1
                i = 0
            else:
                prev = int(sl[i-2])
                i = i-1
        else:
            prev = int(sl[i])
            i += 1

    print(n)

main()
### BUGGY CODE ###

MAX_X = 10 ** 5
buffer = 10 ** 3
prime_flags = [1 for _ in range(MAX_X + buffer)]

for i in range(MAX_X + buffer):
  num = i
  while num < MAX_X + buffer:
    num += i
    prime_flags[num] = 0

X = int(input().strip())
for i, flag in enumerate(prime_flags[X:]):
  if flag == 1:
    print(X + i)
    break
    

### FIXED CODE ###

MAX_X = 10 ** 5
buffer = 10 ** 3
prime_flags = [1 for _ in range(MAX_X + buffer)]

for i in range(2, MAX_X + buffer):
  num = i
  if prime_flags[num] == 0:
    continue
  while num + i < len(prime_flags):
    num += i
    prime_flags[num] = 0

X = int(input().strip())
for i, flag in enumerate(prime_flags[X:]):
  if flag == 1:
    print(X + i)
    break