Harryxun/stf_run huggingface dataset:
INF = 10**10


def partition(ary, p, r):
    x = ary[r][1]
    i = p - 1
    for j in range(p, r):
        if ary[j][1] <= x:
            i += 1
            ary[i], ary[j] = ary[j], ary[i]

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


def quick_sort(ary, p, r):
    if p < r:
        q = partition(ary, p, r)
        quick_sort(ary, p, q - 1)
        quick_sort(ary, q + 1, r)


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(INF)
    rry.append(INF)

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    ary = []
    for line in sys.stdin:
        _ = line.strip().split()
        ary.append((_[0], int(_[1])))

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]



### FIXED CODE ###

INF = 10**10


def partition(ary, p, r):
    x = ary[r][1]
    i = p - 1
    for j in range(p, r):
        if ary[j][1] <= x:
            i += 1
            ary[i], ary[j] = ary[j], ary[i]

    ary[i + 1], ary[r] = ary[r], ary[i + 1]

    return i + 1


def quick_sort(ary, p, r):
    if p < r:
        q = partition(ary, p, r)
        quick_sort(ary, p, q - 1)
        quick_sort(ary, q + 1, r)


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(('INF', INF))
    rry.append(('INF', INF))

    i = 0
    j = 0
    for k in range(left, right):
        if lry[i][1] <= rry[j][1]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    import sys
    from copy import deepcopy

    n = int(input())
    # ary = [(lambda x: (x[0], int(x[1])))(line.strip().split()) for line in sys.stdin]
    ary = [(lambda x: (x[0], int(x[1])))(input().split()) for i in range(n)]

    qary = deepcopy(ary)
    mary = deepcopy(ary)
    quick_sort(qary, 0, n - 1)
    merge_sort(mary, 0, n)

    if qary == mary:
        print('Stable')
    else:
        print('Not stable')
    [print(*_) for _ in qary]
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1

            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)
N,A = map(int,input().split())
if N%500 <= A:
        print("YES")
else:
        print("NO") 
                     

### FIXED CODE ###

N = int(input())
A = int(input())

if N % 500 <= A:
        print("Yes")
else:
        print("No")
import collections

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

S = [0]

def comb(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return comb(n-1,r-1)+comb(n-1,r)

for i in A:
    S.append(S[-1] + i)

count = 0
count_dict = collections.Counter(S)
for i in count_dict.values():
    count += comb(i,2)
print(count)

### FIXED CODE ###

from math import factorial
from collections import Counter

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

S = [0]

for i in A:
    S.append(S[-1] + i)

count = 0
count_dict = Counter(S)
for i in count_dict.values():
    if i == 1:
        continue
    count += factorial(i) // (factorial(i - 2) * factorial(2))
print(count)
W = raw_input().lower()
T = []
while True:
    TL = raw_input()
    if(TL == 'END_OF_TEXT'):
        break
    else:
        T += TL.split()
map(lower, T)
print T.count(W)

### FIXED CODE ###

word = raw_input().lower()
text = []
while True:
    line = raw_input()
    if line == 'END_OF_TEXT':
        break
    else:
        text += line.lower().split()
print text.count(word)
from collections import defaultdict

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  x = 1
  for i in range(1, N+1)
    x = (x * B) % M
    if g[i]:
      sum_g[g[i]] += x
      sum_g[0] -= x
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret += (sx*sy*sz) % M
  return ret%M


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

### FIXED CODE ###

from collections import defaultdict

M = 998244353
B = 10**18 % M

def mex(s):
  for i in range(max(s)+2):
    if i not in s:
      return i

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in sorted(e.keys(), reverse=True):
    m = mex({g.get(j,0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] += x
      sum_g[0] -= x
  return sum_g

def get_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, x in sum_g[0].items():
    for gy, y in sum_g[1].items():
      gz = gx^gy
      z = sum_g[2][gz]
      ret = (ret + x*y*z)%M
  return ret

N = int(input())
edge = [get_edge() for i in range(3)]

print(solve(N, edge))
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
hako = [0]*(max(a)+1)
ind = list(range(max(a)+1))
S = sum(a)
s = []

for i in a:
    hako[i] += 1

for i in range(q):
    b, c = [int(i) for i in input().split()]
    S += (ind[c] - ind[b])*hako[b]
    s.append(S)
    hako[c] += hako[b]
    hako[b] = 0
for i in range(q):
    print(s[i])

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
hako = [0]*(10**6)
ind = list(range(10**6))
S = sum(a)
s = []

for i in a:
    hako[i] += 1

for i in range(q):
    b, c = [int(i) for i in input().split()]
    S += (ind[c] - ind[b])*hako[b]
    s.append(S)
    hako[c] += hako[b]
    hako[b] = 0
for i in range(q):
    print(s[i])
n = int(input())
h = list(map(int, input().split()))
x = h[-1]
ans = "Yes"
for i in reversed(range(n - 1)):
    print(h)
    hi = h[i]
    if hi <= x:
        pass
    else:
        if abs(x - hi) >= 2:
            ans = "No"
        else:
            h[i] -= 1
    x = hi
print(ans)


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
x = h[-1]
ans = "Yes"
for i in reversed(range(n - 1)):
    hi = h[i]
    if hi <= x:
        pass
    else:
        if abs(x - hi) >= 2:
            ans = "No"
        else:
            h[i] -= 1
    x = h[i]
print(ans)
import sys

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

hw = [[0] * W for _ in range(H)]

w = [0] * W
h = [0] * H

for i in range(M):
    h_i, w_j = list(map(int, input().split()))
    hw[h_i-1][w_j-1] = 1
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
for i in range(H):
    for j in range(W):
        d = hw[i][j]
        a = max(a, h[i]+w[j]-d)
print(a)



### FIXED CODE ###

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

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
return x**3

### FIXED CODE ###

x = raw_input()
print int(x)**3
w, h, x, y, r = map ( int, input ( ).split ( ) )
if x-r >=0 and  x+r <= w and y-r >= 0 and y+r <=h:
  print ( "Yes" )
else:
  print ( "No" )

### FIXED CODE ###

w, h, x, y, r = map(int, input( ).split( ))
if x-r >=0 and  x+r <= w and y-r >= 0 and y+r <=h:
  print ( "Yes" )
else:
  print ( "No" )
W,H,x,y,r=list(map(int,input().split()))
if r<=x<=(W-r) and r<=y<=(H-r):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import math
r=float(input())
l=math.pi*r*2
s=(r**2)*math.pi
print("{1:6f} {0:6f}".format(l, s))
from math import factorial

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

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

def func(a_p,a_c):
  if a_p == a_c: return 1
  num_steps = a_c - a_p
  r = 0
  result = 0
  for n in range(num_steps,0,-1):
    result += int(comb(n,r))
    r += 1
    if n <= r: break
  return result

a_p = 0
result = 1
for i in range(M):
  a_c = int(input()) - 1
  
  if a_c + 1 == a_p: 
    result *= 0
  result *= func(a_p,a_c)
  a_p = a_c + 2
  
result *= func(a_p,N)
print(result%1000000007)

### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e6))
N, M = map(int,input().split())


def func(n):
    """メモ化フィボナッチ"""
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1)%1000000007 + _fib(n-2)%1000000007
        return memo[n]

    return _fib(n)

a_p = 0
result = 1
for i in range(M):
  a_c = int(input()) - 1
  
  if a_c + 1 == a_p: 
    print(0)
    quit()
  result = ((func(a_c - a_p + 1)%1000000007) * (result%1000000007))%1000000007
  a_p = a_c + 2
  
result = ((func(N - a_p + 1)%1000000007) * (result%1000000007))%1000000007
print(result)
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0
    def __str__(self):
        print(f'i={i},j={j},isblack={isblack},distance={distance}')

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

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='#'))
    g.append(gi)

d=deque()

# 黒マスのreachedをTrueにし，dequeに入れる
for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:
#        print(grid.distance,end=' ')
#    print()
'''

print(max([max([grid.distance for grid in row]) for row in g]))

### FIXED CODE ###

from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0

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

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='#'))
    g.append(gi)

d=deque()

# 黒マスのreachedをTrueにし，dequeに入れる
for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:
#        print(grid.distance,end=' ')
#    print()
'''

print(max([max([grid.distance for grid in row]) for row in g]))
while True:
  a,op,b = input().split()
  
  if op=='?':
    break
  elif  op=='+':
    print("{:d}".format(a+b))
  elif op=='-':
    print("{:d}".format(a-b))
  elif op=='/':
    print("{:d}".format(a//b))
  elif op=="*":
    print("{:d}".format(a*b))


### FIXED CODE ###

while True:
  a,op,b = input().split()
  a=int(a)
  op=str(op)
  b=int(b)
  
  if op=='?':
    break
  elif  op=='+':
    print("{:d}".format(a+b))
  elif op=='-':
    print("{:d}".format(a-b))
  elif op=='/':
    print("{:d}".format(a//b))
  elif op=="*":
    print("{:d}".format(a*b))
import math

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

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

print(lcm(A, B))

### FIXED CODE ###

from fractions import gcd

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

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

print(lcm(A, B))
#!/usr/bin/env python3
import sys
import copy

MOD = 2  # type: int

def solve(N: int, A: "List[int]"):
    ans = []
    for i in range(N,0,-1):
        c = 0
        for j in range(2,N + 1):
            if i * j <= N:
                if A[i*j-1] == 1:
                    c += 1
        if A[i-1] == 0:
            if c % 2 == 1:
                ans.append(i)
        else:
            if c % 2 == 0:
                ans.append(i)

    print(len(ans))
    for i in ans:
        print(f"{i} ",end="")

    print("")

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 2  # type: int

def solve(N: int, A: "List[int]"):
    ans = set()
    for i in range(N,0,-1):
        c = 0
        for j in range(2,N + 1):
            if i * j <= N:
                if i*j in ans:
                    c += 1
            else:
                break

        if A[i-1] == 0:
            if c % 2 == 1:
                ans.add(i)
        else:
            if c % 2 == 0:
                ans.add(i)

    print(len(ans))
    if len(ans):
        print(" ".join([str(i) for i in ans]))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
k = 0 
for i in range(N-1,-1,-1):
    if A[i] % B[i] == 0 :
        continue
    else :
        c = (B[i] - A[i] % B[i])
        k += c
        for j in range(i):
            A[j] += c

print(k)

### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
k = 0 
for i in range(N-1,-1,-1):
    A[i] += k
    if A[i] % B[i] == 0 :
        pass
    else :
        c = (B[i] - A[i] % B[i])
        k += c

print(k)
#include <iostream>
#include <string>
using namespace std;


int main()
{
  string s;
  int c=0;
  
  cin >> s;
  for ( int i=0; i<s.length(); i++ ) {
    if ( s[i] == '1' ) c++;
  }
  cout << c << endl;
  
  return 0;
}


### FIXED CODE ###

def main():
    print(input().count('1'))


if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


import numpy as np
import bisect

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
A.sort()
for _ in range(M):
    b, c = map(int, input().split())
    index = bisect.bisect_left(A, c)
    edge = max(0, index - b)
    A[:edge] = A[index-edge:index]
    A[edge:index] = c

print(sum(A))


### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1
for i in range(M):
    b, c = map(int, input().split())
    d[c] += b
    

key = sorted(list(d.keys()))

num = N
i = 0
S = 0
while num > 0:
    i -= 1
    n = d[key[i]]
    num -= n
    S += key[i] * n
    
S += key[i] * num

print(S)
s = input().strip()

t = 'AKIHABARA'
ti = 0
result = True

for i in range(len(s)):
    if s[i] == t[ti]:
        ti += 1
    elif s[i] == 'A':
        continue
    else:
        result = False

if result:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

s = input().strip()

t = 'AKIHABARA'
si = 0
result = True

if len(s) > len(t):
    print('NO')
    exit()

for ti in range(len(t)):
    if si >= len(s):
        if t[ti:] == 'A' * (len(t) - ti):
            result = True
        else:
            result = False
        break
    elif s[si] == t[ti]:
        si += 1
    elif t[ti] == 'A':
        continue
    else:
        result = False
        break

if result:
    print('YES')
else:
    print('NO')
N = int(input())
dp = [0,0,0]
for _ in range(N):
    a, b, c = map(int, input().split())
    ndp = [0,0,0]
    ndp[0] = max(dp[1], dp[2]) + a
    ndp[1] = max(dp[0], dp[2]) + b
    ndp[2] = max(dp[0], dp[1]) + c
    dp = ndp
return max(dp)


### FIXED CODE ###

N = int(input())
dp = [0,0,0]
for _ in range(N):
    a, b, c = map(int, input().split())
    ndp = [0,0,0]
    ndp[0] = max(dp[1], dp[2]) + a
    ndp[1] = max(dp[0], dp[2]) + b
    ndp[2] = max(dp[0], dp[1]) + c
    dp = ndp
print(max(dp))
N = int(input())
S = list(input())

while S[-1] != ".":
    S.pop()
N = len(S)

if N == 0:
    print(0)

ans = 0
T1 = S.copy()
f = False
for i in range(N):
    s = T1[i]
    if s == ".":
        continue
    else:
        if i < N - 1 and T1[i+1] == ".":
            if not f and i + 1 < N - 1 and T1[i+2] == ".":
                ans += 1
            else:
                f = True
                T1[i+1] = "#"
                ans += 1
        else:
            f = True
ans2 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        continue
    else:
        ans2 += 1

ans3 = 0

for i in range(N):
    s = S[i]
    if s == ".":
        ans3 += 1
    else:
        continue
print(min(ans2, ans, ans3))



### FIXED CODE ###

N = int(input())
S = list(input())

acc = [0]
acc2 = [0]
for s in S:
    if s == ".":
        acc.append(acc[-1] + 1)
        acc2.append(acc2[-1])
    else:
        acc.append(acc[-1])
        acc2.append(acc2[-1] + 1)
acc.pop(0)

ans = float("inf")

for i in range(N):
    s = S[i]
    tmp = acc[-1] - acc[i]
    tmp2 = acc2[i]
    ans = min(ans , tmp + tmp2)
print(ans)