Harryxun/stf_run huggingface dataset:
import sys
import heapq
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()


hpop = heapq.heappop
hpush = heapq.heappush

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  hpush(node, [nextx - x, xID, nextxID])
  hpush(node, [nexty - y, yID, nextyID])

ans = 0
while node:
  val, i, j = hpop(node)
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)
# -*- coding: utf-8 -*-

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

n = max([int(a / d) + 1, int (c / b) + 1])

for i in range(n):
    a -= d
    c -= b
    # print(a,c)
    if c <= 0:
        print('Yes')
        exit()
    elif a <= 0:
        print('No')
        exit()

### FIXED CODE ###

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

n = int(input())

kind = []

for i in range(n):
    kind.append(input())

print(len(set(kind)))
n = int(input())
s = input()
D = [[0] * n for i in range(n)]
 
for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

for i in range(1,n):
    for j in range(i+1,n):
        print(f"i,j = {i,j}")
        mae = D[i-1][j-1]
        print(f"mae = {mae}")
        if s[i] == s[j]:
            if j-i <= mae:
                D[i][j] = mae
            else:
                D[i][j] = mae + 1

print(max([max(D[i]) for i in range(n)]))


### FIXED CODE ###

n = int(input())
s = input()
D = [[0] * n for i in range(n)]
 
for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

for i in range(1,n):
    for j in range(i+1,n):
        mae = D[i-1][j-1]
        if s[i] == s[j]:
            if j-i <= mae:
                D[i][j] = mae
            else:
                D[i][j] = mae + 1

print(max([max(D[i]) for i in range(n)]))
import sys
input=sys.stdin.readline
a = input()
while (int(a) != 0):
    remain = [0for i in range(2019)]
    remain[int(a[0])] = remain[int(a[0])] + 1  ##V0
    n = len(a)
    cnt = 0
    for i in range(1,n):
        copy = remain[:]
        remain = [0for i in range(2019)]
        a_i = int(a[i])
        if (a_i != 0):
            for k in range(2019):
                rem = (k*10 + a_i)%2019
                remain[rem] += copy[k]
            remain[a_i] += 1
        elif (a_i == 0):
            for k in range(2019):
                rem = (k*10 + a_i)%2019
                remain[rem] += copy[k]
        cnt += remain[0]
    print(cnt)
    exit(0)

### FIXED CODE ###


"""
：余りの等しい物をカウントし、その累積和
：Aの余りとBの余り(mod 2019)が等しい場合
　A-Bは2019の倍数である
：計算量を抑えるため各項と１０の指数乗は分けて計算する
：
"""

import sys
input=sys.stdin.readline
s = input()[:-1][::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0

for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
a=0

while True:
    z=str(input())
    for i in z:
        k=int(i)
        a+=k
    print(a)
    a=0
    if z == 0 :  
        break

### FIXED CODE ###

while True:
    z=list(map(int,(list(str(input())))))
    if z[0]==0:
        break
    print(sum(z))
import math
a,b=map(int,input().split())
bb=math.factorial(b-2)
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
def s(i,d,g):
  g[i]=1
  global e
  global bb
  if i==0:
    f=bb*(b-1)//math.factorial(b-len(d[i])-1)
  else:
    if len(d[i])==0:
      f=1
    else:
      f=bb//math.factorial(b-len(d[i])-1)   
  e=(e*f)%1000000007
  for j in range(len(d[i])):
    if g[d[i][j]]==0:
      s(d[i][j],d,g)
  return

i=0
e=b
s(i,d,g)
print(e%1000000007)
  

### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=deque()
q.append(0)
e=b
while len(q):
  i=q.pop()
  h=len(d[i])
  g[i]=1
  if i==0:
      f=b-1
  else:
    f=b-2
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])
      e=(e*f)%1000000007
      f-=1


print(e%1000000007)
A,B,C,D,E,F=map(int,input().split())
conc = 0.0
liq,sug=0,0
for a in range(31):
  for b in range(16):
    for c in range(31):
      for d in range(16):
        if 100*a+100*b+c+d <= F and  c+d <= (a+b)*E:
          if conc < 100*(c+d)/(100*(a+b)+c+d):
            conc = 100*(c+d)/(100*(a+b)+c+d)
            liq = 100*(a+b)
            sug = c+d
print(liq,sug)

### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())
conc = 0.0
liq,sug = 100*A,0
for a in range(1 + F//(100*A)):
  for b in range(1 + (F-100*A*a)//(100*B)):
    if a + b < 1 or F <= 100*(A*a + B*b):
      break
    for c in range(1 + min(((A*a+B*b)*E)//C,F-100*(A*a+B*b))):
      for d in range(1 + min(((A*a+B*b)*E-C*c)//D,F-100*(A*a+B*b)-C*c)):
        tmp_sug = C*c+D*d
        tmp = 100*(A*a+B*b)+tmp_sug
        if tmp <= F and tmp_sug <= (A*a+B*b)*E and conc < (100*tmp_sug/tmp):
          conc = (100*tmp_sug/tmp)
          liq = tmp
          sug = tmp_sug
print(liq,sug)
N, K = [int(_) for _ in input().split()]
t_and_d = [[int(_) for _ in input().split()] for _ in range(N)]

t_and_d.sort(key=lambda x: x[1], reverse=True)
over_stock = []
type_set = set()

for t_i, d_i in t_and_d[:K]:
    if t_i in type_set:
        over_stock += [d_i]
    else:
        type_set.add(t_i)

x = len(type_set)
point = sum([d for t, d in t_and_d[:K]]) + x ** 2
point_max = point

if over_stock:
    for t_i, d_i in t_and_d[K:]:
        if t_i in type_set:
            continue
        else:
            diff = (x + 1) ** 2 - x ** 2 + d_i - over_stock.pop()
            type_set.add(t_i)
            x += 1
            point += diff
            point_max = max(point_max, point)

print(point_max)


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
t_and_d = [[int(_) for _ in input().split()] for _ in range(N)]
t_and_d.sort(key=lambda x: x[1], reverse=True)

over_stock = []
type_set = set()

for t_i, d_i in t_and_d[:K]:
    if t_i in type_set:
        over_stock += [d_i]
    else:
        type_set.add(t_i)

x = len(type_set)
point = sum([d for t, d in t_and_d[:K]]) + x ** 2
point_max = point

for t_i, d_i in t_and_d[K:]:
    if over_stock:
        if t_i in type_set:
            continue
        else:
            diff = (x + 1) ** 2 - x ** 2 + d_i - over_stock.pop()
            type_set.add(t_i)
            x += 1
            point += diff
            point_max = max(point_max, point)

print(point_max)
n=input()
p= len(n)

o = 0

for i in range(p):
    if i % 2 == 0:
        if n[i] == '0':
            o= o+1
            
    else:
        if n[i] =='1':
            o= o+1

if ans>p/2:
    print(p-o)
else:
    print(o)

### FIXED CODE ###


m=input()
round = len(m)

n = 0

for i in range(round):
    if i % 2 == 0:
        if m[i] == '0':
            n = n+1
            
    else:
        if m[i] =='1':
            
            n = n+1

if n>round/2:
    print(round-n)
else:
    print(n)
print(int(input())*int(input()))


### FIXED CODE ###

a,b = map(int, input().split());
print(a*b);
a,op,b = map(raw_input().split())
if op=="+":
    print a+b
else:
    print a-b


### FIXED CODE ###

array = map(str, raw_input().split())
# print array
if array[1]=="+":
    print int(array[0])+int(array[2])
else:
    print int(array[0])-int(array[2])
N, Y = list(map(int, input().split()))

q = [(N, 0, 0)]
while len(q) > 0:
    hyp = q.pop()
    num = hyp[0] + hyp[1] + hyp[2]
    currency = 10000 * hyp[0] + 5000 * hyp[1] + 1000 * hyp[2]
    if num == N and currency == Y:
        q.append(hyp)
        break
    if currency < Y:
        continue
    
    #### 10000円札 → 5000円札 x 2 の場合
    q.append((hyp[0] - 1, hyp[1] + 1, hyp[2]))
    q.append((hyp[0] - 1, hyp[1], hyp[2] + 1))

    #### 5000円札 x 1 → 1000円札 x 5 の場合
    if hyp[1] >= 1:
        q.append((hyp[0], hyp[1] - 1, hyp[2] + 1))

if len(q) > 0:
    print(f"{q[-1][0]} {q[-1][1]} {q[-1][2]}")
else:
    print("-1 -1 -1")

### FIXED CODE ###

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

result = (-1, -1, -1)
for x in range(N + 1):
    for y in range(N + 1):
        if x + y > N:
            break
        if 10000 * x + 5000 * y + 1000 * (N - x - y) == Y:
            result = (x, y, N - x - y)
print("{} {} {}".format(result[0], result[1], result[2]))
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
#n = int(input())
#L = list(map(int, input().split()))
#import math
#import sys
#import heapq
#import fractions
#import bisect
#import numpy




NM = list(map(int, input().split()))
ps = [list(input().split()) for i in range(NM[1])]
a=[0]*NM[0]
flg = [True]*NM[0]
for i in range(NM[1]):
    ps[i][0] = int(ps[i][0])

ans = [0]*NM[0]
ac = 0
for i in range(NM[1]):
    if ps[i][1] == "AC":
        flg[ps[i][0]-1] = False
        ans[ps[i][0]-1] = a[ps[i][0]-1]
    if ps[i][1] == "WA" and flg[ps[i][0]-1]:
        a[ps[i][0]-1] += 1

for i in range(NM[0]):
    if flg[i]== False:
        ac += 1
print(ac,sum(ans))#n = int(input())
#L = list(map(int, input().split()))
#import math
#import sys
#import heapq
#import fractions
#import bisect
#import numpy




NM = list(map(int, input().split()))
ps = [list(input().split()) for i in range(NM[1])]
a=[0]*NM[0]
flg = [True]*NM[0]
for i in range(NM[1]):
    ps[i][0] = int(ps[i][0])

ans = [0]*NM[0]
ac = 0
for i in range(NM[1]):
    if ps[i][1] == "AC":
        flg[ps[i][0]-1] = False
        ans[ps[i][0]-1] = a[ps[i][0]-1]+1
    if ps[i][1] == "WA" and flg[ps[i][0]-1]:
        a[ps[i][0]-1] += 1

for i in range(NM[0]):
    if flg[i]== False:
        ac += 1
print(ac,sum(ans)-ac)
        



        




### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
#import math
#import sys
#import heapq
#import fractions
#import bisect
#import numpy




NM = list(map(int, input().split()))
ps = [list(input().split()) for i in range(NM[1])]
a=[0]*NM[0]
flg = [True]*NM[0]
for i in range(NM[1]):
    ps[i][0] = int(ps[i][0])

ans = [0]*NM[0]
ac = 0
for i in range(NM[1]):
    if ps[i][1] == "AC" and flg[ps[i][0]-1]:
        flg[ps[i][0]-1] = False
        ans[ps[i][0]-1] = a[ps[i][0]-1]
    if ps[i][1] == "WA" and flg[ps[i][0]-1]:
        a[ps[i][0]-1] += 1

for i in range(NM[0]):
    if flg[i]== False:
        ac += 1
print(ac,sum(ans))
std_n = int(input())
std_list = tuple(map(int, input().split()))
std_set = set(std_list)

if std_set == {0}:
    print("Yes")
elif len(std_set) == 2:
    if 0 in std_set:
        if std_list.count(0) * 3 == std_n:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
elif len(std_set) == 3:
    a, b, c = tuple(std_set)
    if (std_list.count(a) == std_list.count(b)) and (std_list.count(b) == std_list.count(c)):
        if int(str(int(format(a, "b")) ^ int(format(b, "b"))), 2) == c:
            print("Yes")
        else:
            print("No")
    else:
        print("No")
else:
    print("No")


### FIXED CODE ###

std_n = int(input())
std_list = tuple(map(int, input().split()))
std_set = set(std_list)

if std_set == {0}:
    print("Yes")
    exit()
elif len(std_set) == 2:
    if 0 in std_set:
        if std_list.count(0) * 3 == std_n:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()
elif len(std_set) == 3:
    a, b, c = tuple(std_set)
    if (std_list.count(a) == std_list.count(b)) and (std_list.count(b) == std_list.count(c)):
        if a ^ b == c:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
    else:
        print("No")
        exit()
else:
    print("No")
    exit()

############


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

unq = list(set(nums))


def answer(ans):
    print(ans)
    exit()


if len(unq) > 3:
    answer("No")

if len(unq) == 3:
    a, b, c = unq
    if a ^ b ^ c != 0:
        answer("No")
    if nums.count(a) == nums.count(b) == nums.count(c):
        answer("Yes")
    else:
        answer("No")

if len(unq) == 2:
    a, b = sorted(unq)
    if a != 0:
        answer("No")
    if nums.count(a) * 2 == nums.count(b):
        answer("Yes")
    else:
        answer("No")

if len(unq) == 1:
    a = unq[0]
    if a != 0:
        answer("No")
    else:
        answer("Yes")
import math
import sys
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
  
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

C = gcd_list(A)
B = [0 for _ in range(N)]

for i in range(N):
  B[i] = C // A[i]
  if B[i] % 2 == 0:
    print(0)
    sys.exit()

print( (M // C + 1) // 2)

### FIXED CODE ###

import math
import sys
from functools import reduce

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

for i in range(N):
  A[i] = A[i] // 2
  
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
  
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

C = lcm_list(A)
B = [0 for _ in range(N)]

for i in range(N):
  B[i] = C // A[i]
  if B[i] % 2 == 0:
    print(0)
    sys.exit()

print( (M // C + 1) // 2)
n = int(input())
p = list(map(int,input().split()))
ans = 1
l = []

for i in range(1,n+1):
    l = p[0:i]
    if p[i] <= min(l):
        ans += 1
    else:
        pass

print(ans)


### FIXED CODE ###


n = int(input())
p = list(map(int,input().split()))
ans = 0
currentMin = 10 ** 9
s = []

for i in range(n):
    if currentMin > min(currentMin,p[i]):
        currentMin = min(currentMin,p[i])
        s.append(currentMin)
    else:
        s.append(currentMin)

for i in range(len(p)):
    if p[i] == s[i]:
        ans += 1

print(ans)
x,y,z=input().split()
print(x[0]+y[1]+z[2])

### FIXED CODE ###

x = input()
y = input()
z = input()
print(x[0]+y[1]+z[2])
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    acc = {}
    for i in range(N):
        for j in range(i+1, N):
            dx = x[i] - x[j]
            dy = y[i] - y[j]
            c = gcd(dx, dy)
            tmp = (dx // c, dy // c)
            acc.setdefault(tmp, set()).add(j)
    return N - max([len(s) for s in acc.values()])


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
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, x: "List[int]", y: "List[int]"):
    ds = []
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx = x[j] - x[i]
            dy = y[j] - y[i]
            ds.append((dx, dy))

    return 1 if N == 1 else (N - max(Counter(ds).values()))


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
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    print(result)

if __name__ == '__main__':
    main()
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(2):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)

### FIXED CODE ###

S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(3):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)
N,Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  s = S[l-1:r]
  print(s)


### FIXED CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
s = input()
c = 0
for i in range(3):
    if a[i] == 1:
        c = c + 1
return c

### FIXED CODE ###

a = input()
c=0
for i in range(len(a)):
    if a[i] == '1':
        c = c + 1
print(c)
while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    y = 0
    while y ** 2 <= e:
        z = 0
        while y ** 2 + z ** 3 <= e:
            x = e - y ** 2 - z ** 3
            m = min(m, x + y + z)
            z += 1
        y += 1
    print(m)
    


### FIXED CODE ###

import math

while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    z = 0
    while z <= e:
        z3 = z ** 3
        if z3 > e:
            break
        y = int(math.sqrt(e - z3))
        x = e - y ** 2 - z3
        m = min(m, x + y + z)
        z += 1
    print(m)
import sys

def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    data = range(1, M+1)
    A = []
    for i in range(len(data)):
        for j in range(i, len(data)):
            for k in range(j, len(data)):
                A.append([data[i], data[j], data[k]])
    l = []
    m = 0
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        l.append([a, b, c, d])
    for a_list in A:
        tmp = 0
        for i in l:
            if a_list[i[1] -1] - a_list[i[0] - 1] == i[2]:
                tmp += i[3]
        if tmp > m:
            m = tmp
    return m


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import sys
import itertools

def main():
    input = sys.stdin.readline
    N, M, Q = map(int, input().split())
    data = range(1, M+1)
    A = list(itertools.combinations_with_replacement(range(1, M+1), N))
    l = []
    m = 0
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        l.append([a, b, c, d])
    for a_list in A:
        tmp = 0
        for i in l:
            if a_list[i[1] -1] - a_list[i[0] - 1] == i[2]:
                tmp += i[3]
        if tmp > m:
            m = tmp
    return m


if __name__ == '__main__':
    print(main())
n=input()
n.replace(1,x)
n.replace(9,1)
print(n.replace(x,9))

### FIXED CODE ###

n=input()
n=n.replace('1','x')
n=n.replace('9','1')
n=n.replace('x','9')
print(n)
n = input()

print(n[0] + str(len(s) + n[len(s)-2]))

### FIXED CODE ###

s = input()
N = len(s)
print(s[0] + str(N - 2) + s[N - 1])