Harryxun/stf_run huggingface dataset:
def main():
  import sys
  b=sys.stdin.buffer
  n=int(b.readline())
  d=[0]*n+[1<<c-97for c in b.readline()[:n]]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  for q,a,b in zip(*[iter(b.read().split())]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i:
        i//=2
        d[i]=d[i+i]|d[i-~i]
      continue
    j=int(b)+n
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i//=2
      j//=2
    r+=bin(s).count('1'),
  print(' '.join(map(str,r)))
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
n, m = map(int, input().split())
x = list(map(int, input().split()))

if m == 1:
    print('0')
    exit()
if n >= m:
    print(0)
    exit()

x = sorted(x)
prev = x[0]
diff = []
for i, v in enumerate(x[1:]):
    diff.append([i, abs(prev-v)])
    prev = v

diff = sorted(diff, key=lambda x: x[1], reverse=True)

split_index = list(map(lambda x: x[0]+1, diff[:n-1]))

ans = x[split_index[-1]:][-1] - x[split_index[-1]:][0]
index_from = 0
for i in range(n-1):
    index_to = split_index[i]
    ans += (x[index_from:index_to][-1] - x[index_from:index_to][0])
    index_from = index_to
print(ans)

### FIXED CODE ###

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

if n >= m:
    print(0)
    exit()

a = sorted(a)
diff = []
for i in range(1, m):
    diff += [abs(a[i] - a[i-1])]

diff = sorted(diff, reverse=True)

ans = a[-1] - a[0]
for i in range(n-1):
    ans -= diff[i]

print(ans)
#ABC070
n = int(input())
t = []
for i in range(n):
    t.append(int(input()))

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return int(a*b/gcd(a,b))

# a,b,cの最小公倍数→lcm(lcm(a,b),c)で表される

# t[i]の最小公倍数を求めればよい。
res=t[0]
for i in range(1,n):
    res = lcm(res,t[i])
print(res)

### FIXED CODE ###

n = int(raw_input())

def gcd(a,b):
    if a > b:
        a,b = b,a
    # a <= b
    while a > 0:
        a,b = b%a, a
    return b

def lcm(a,b):
    g = gcd(a,b)
    return a/g * b

x = 1
for i in range(n):
    ti = int(raw_input())
    x = lcm(x, ti)

print x
N = input()

a = 0

for val in range(1, N+1):
  if val%3 != 0 and val%3 != 0:
    a += val
  
print(a)

### FIXED CODE ###

N = int(input())

a = 0

for val in range(1, N+1):
  if val%3 != 0 and val%5 != 0:
    a += val
  
print(a)
O = input()
E = input()
for i in range(len(O)):
    print(O[i],end="")
    print(E[i],end="")

### FIXED CODE ###

O = input()
E = input()

if len(O) > len(E):
    for i in range(len(E)):
        print(O[i],end="")
        print(E[i],end="")
    print(O[i+1])
elif len(O) < len(E):
    for i in range(len(O)):
        print(E[i],end="")
        print(O[i],end="")
    print(O[i+1])
else:
    for i in range(len(O)):
        print(O[i],end="")
        print(E[i],end="")
A, B = map(int, input().split())

if A >= B: print(2*A)
elif: print(2*B) 
  

### FIXED CODE ###

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

if A > B: print(2*A-1)
elif A == B: print(2*A)
else: print(2*B-1)
a=int(input())
list=[]

for i in range(a):
    order=input().split()
    if order[0]=="insert":
        list.appendleft(order[1])
    elif order[0]=="delete":
        if order[1] in list:
            list.remove(order[1])
    elif order[0]=="deleteFirst":
        list.pop(0)
    elif order[0]=="deleteLast":
        list.pop(len(list)-1)

print(*list)


### FIXED CODE ###

from collections import deque
a=int(input())
list=deque([])

for i in range(a):
    order=input().split()
    if order[0]=="insert":
        list.appendleft(order[1])
    elif order[0]=="delete":
        if order[1] in list:
            list.remove(order[1])
    elif order[0]=="deleteFirst":
        list.popleft()
    elif order[0]=="deleteLast":
        list.pop()

print(*list)
n = input()

color = [0 for i in range(100)]
d = [0 for i in range(100)]
f = [0 for i in range(100)]
M = [0 for i in range(n)]0 for j in range(n)]

def dfs_v(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 1 and color[v] == 0:
      dfs_v(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  t = 0
  for u in range(n):
    if color[u] == 0:
      dfs_v(u)
  for u in range(n):
    print u+1, d[u], f[u]

for i in range(n):
  X = map(int, raw_input().split())
  for j in range(X[1]):
   M[X[0]] [X[2+j]-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
n,k,p=map(int,input().split()),998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]]
print(sum(f[-1]*pow(f[i]*f[-1-i],-1,p)for i in r(n-1,k))%p)

### FIXED CODE ###

n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=0
for i in r(n-1,k):a+=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)
seven = 7
n = int(input())
if n.find(seven) = 7: 
  print('Yes')
else: 
  print('No)

### FIXED CODE ###

n = input()
if '7' in n: 
  print('Yes')
else: 
  print('No')
nm = list(map(int, (input().split())))
if nm[1] == 0:
    print(0, 0)

else:    
    ans_dict = {}
    ans_list = [input().split() for i in range(nm[1])]
    for i in range(len(ans_list)):
        key_val = ans_list[i][0]

        try:
            ans_dict[key_val].append(ans_list[i][1])
        except:
            ans_dict[key_val] = [ans_list[i][1]]
    ans_cnt = 0
    wa_cnt = 0
    for key_val in ans_dict.keys():
        check_list = ans_dict[key_val]

        if "AC" in check_list:
            ans_cnt += 1
        else:
            pass
        try:
            wa_cnt += len(check_list[:check_list.index("AC")])
        except:
            pass
print(ans_cnt, wa_cnt)    

### FIXED CODE ###

nm = list(map(int, (input().split())))
if nm[1] == 0:
    print(0, 0)

else:    
    ans_dict = {}
    ans_list = [input().split() for i in range(nm[1])]
    for i in range(len(ans_list)):
        key_val = ans_list[i][0]

        try:
            ans_dict[key_val].append(ans_list[i][1])
        except:
            ans_dict[key_val] = [ans_list[i][1]]
    ans_cnt = 0
    wa_cnt = 0
    for key_val in ans_dict.keys():
        check_list = ans_dict[key_val]

        if "AC" in check_list:
            ans_cnt += 1
        else:
            pass
        try:
            wa_cnt += len(check_list[:check_list.index("AC")])
        except:
            pass
    print(ans_cnt, wa_cnt)
x = list(input())
first = 10 * int(x[0]) + int(x[1])
second = 10 * int(x[2]) + int(x[3])


def mc(num):
    if 1 <= num <= 12:
        return True
    else:
        return False


def yc(num):
    if 1 <= num <= 99:
        return True
    else:
        return False


if yc(first):
    if mc(second):
        if yc(second):
            if mc(first):
                print("AMBIGUOUS")
            else:
                print("YYMM")
        else:
            print("YYMM")
    elif yc(second):
        if mc(first):
            print("MMYY")
        else:
            print("NA")
    else:
        pirnt("NA")
elif yc(second):
    if mc(first):
        print("MMYY")
    else:
        print("NA")
else:
    print("NA")


### FIXED CODE ###

x = list(input())
first = 10 * int(x[0]) + int(x[1])
second = 10 * int(x[2]) + int(x[3])


def mc(num):
    if 1 <= num <= 12:
        return True
    else:
        return False


def yc(num):
    if 0 <= num <= 99:
        return True
    else:
        return False


if yc(first):
    if mc(second):
        if yc(second):
            if mc(first):
                print("AMBIGUOUS")
            else:
                print("YYMM")
        else:
            print("YYMM")
    elif yc(second):
        if mc(first):
            print("MMYY")
        else:
            print("NA")
    else:
        print("NA")
elif yc(second):
    if mc(first):
        print("MMYY")
    else:
        print("NA")
else:
    print("NA")
def main():
    N = int(input())
    S = input()
    lst = list(S)

    a = ['{:03d}'.format(i) for i in range(1000)]
    count = 0
    for i in range(len(a)):
        m,n,o = 0,1,2
        s = list(a[i])
        while m < n < o < len(lst) :
            if s[0] != lst[m]:
                m += 1
                n += 1
                o += 1
            elif s[1] != lst[n]:
                n += 1
                o += 1
            elif s[2] != lst[o]:
                o += 1
            else:
                count += 1
                break

    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    M1, D1  = list(map(int, input().split()))
    M2, D2  = list(map(int, input().split()))

    if D2 == 1 and M1 != M2:
        print(1)
    else:
        print(0)
    
    
if __name__ == "__main__":
    main()
from collections import defaultdict

params = input().split()
n = int(params[0])
m = int(params[1])

penaltyCount = dict()
penaltyCount = defaultdict(lambda: 0, penaltyCount)

correct = 0
penalty = 0

for i in range(m):
    submission = input.split()
    p = int(submission[0]) - 1
    status = submission[1]

    if penaltyCount[p] == -1:
        continue
    if status == "WA":
        penaltyCount[p] += 1
    else:
        penalty += penaltyCount[p]
        penaltyCount[p] = -1
        correct += 1

print(str(correct) + " " + str(penalty))



### FIXED CODE ###

from collections import defaultdict

params = input().split()
n = int(params[0])
m = int(params[1])

penaltyCount = dict()
penaltyCount = defaultdict(lambda: 0, penaltyCount)

correct = 0
penalty = 0

for i in range(m):
    submission = input().split()
    p = int(submission[0]) - 1
    status = submission[1]

    if penaltyCount[p] == -1:
        continue
    if status == "WA":
        penaltyCount[p] += 1
    else:
        penalty += penaltyCount[p]
        penaltyCount[p] = -1
        correct += 1

print(str(correct) + " " + str(penalty))
k = int(input())

cnt = 0
mod = 7%k
period = [mod]

for i in range(1,k+1):
    if mod == 0:
        ans = i
        break
    mod = (mod*10 + 7)%k
    period.append(mod)
    if period[i] == period[0]:
        ans = -1
        break

print(ans)

### FIXED CODE ###

k = int(input())

mod = 7%k
path = [mod]
ans = '-1'

for i in range(1,k+1):
    if mod == 0:
        ans = i
        break
    mod = (mod*10 + 7)%k
    path.append(mod)
    if mod == path[0]:
        ans = '-1'
        break

print(ans)
n = int(input()))
for i in range(n):
    M = [0] * n
    u = list(map(int, input().split()))
    v = u[0]
    k = u[1]
    for j in range(k):
        M[u - 1][v - 1] = 1

for i in range n:
    for j in range n:
        if (j):
            print(" ")
        print(M[i-1][j-1]

### FIXED CODE ###

n = int(input())
M = [[0] * n for i in range (n)]
for i in range(n):
    u = list(map(int, input().split()))
    v = u[0]
    for j in u[2:]:
        M[v - 1][j - 1] = 1

for i in M:
    print(*i)
n=int(input())
mod=10**9+7
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict(AGC=1,ACG=1,GAC=1)
dic4=dict(AGTC=1,AGGC=1,ATGC=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans*=4
        ans%=mod
        for j in range(len(z)):
            for k in range(4):
                f=0
                s=z[1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
    print(ans%mod)
                


### FIXED CODE ###

n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=[]
for j in zt:
    if not j in ng:
        z.append(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   # if not z[i] in ng:
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            #if not z[k] in ng:
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (501) for _ in range(501)], dtype=np.int32)  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(M):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30

### FIXED CODE ###

import numpy as np

N, M, Q = map(int, input().split())
data = [[0] * (N+1) for _ in range(N+1)]

for i in range(M):
    l, r = map(int, input().split())
    data[l][r] += 1

data = np.array(data)
np.cumsum(data, axis=0, out=data)
np.cumsum(data, axis=1, out=data)
data = data.tolist()
#print(data)
for i in range(Q):
    p, q = map(int, input().split())
    p -= 1
    x = data[q][q]
    x -= data[p][q] + data[q][p]
    x += data[p][p]
    print(x)
import bisect

# LIS
N = int(input())
L = list(map(int, input().split()))
L.sort()

# shorter first
# c > b >a
for i in range(0, N-2):
  for j in range(i+1, N-1):
    index = bisect.bisect_left(L, L[i]+L[j])
    count += max(0, index-(j+1))

### FIXED CODE ###

import bisect

# LIS
N = int(input())
L = list(map(int, input().split()))
L.sort()

# shorter first
# c > b >a
count = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    index = bisect.bisect_left(L, L[i]+L[j])
    count += max(0, index-(j+1))
print(count)
# coding=utf-8
# Date: 2020-01-08
# Author: lee215
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))


### FIXED CODE ###

# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

cnt = [0]*(10**5)
cnt2 = [0]*(10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        # print("i: " + str(i))
        # print("nxt: " + str(nxt))
        loop = i - cnt2[nxt]
        modC = max(0, cnt2[nxt])
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop
# print("-------")
# print(t)
# print("modC: " + str(modC))
# print("modK: " + str(modK))
# print("loop: " + str(loop))
# print(modK)
# print(loop)
# print("-------")

print(t[modC + modK] + 1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1

cnt = [0]*(2*10**5)#何回出たか
cnt2 = [0]*(2*10**5)#何回目に出てきたか
t = []
nxt = 0
loop = 0

for i in range(2*10**5):
    cnt[nxt] += 1
    if cnt[nxt] >= 2:
        # print("i: " + str(i))
        # print("nxt: " + str(nxt))
        loop = i - cnt2[nxt]
        modC = cnt2[nxt]
        break
    cnt2[nxt] = i
    t.append(nxt)
    nxt = a[nxt]

modK = (k-modC)%loop
# print("-------")
# print(t)
# print("modC: " + str(modC))
# print("modK: " + str(modK))
# print("loop: " + str(loop))
# print(modK)
# print(loop)
# print("-------")

if k < modC:
    print(t[k] + 1)
else:
    print(t[modC + modK] + 1)

"""
発想はあってる
テストケース公開されたら試してみる！
"""
num_problems = int(input())
a = input()
seconds_per = a.split()
drinks = int(input())
for i in range(drinks):
  b = input()
  c = b.split()
  question = int(c[0])
  change = int(c[1])
  copy = seconds_per[question-1]
  seconds_per[question-1] = change
  print(sum(seconds_per))
  seconds_per[question-1] = copy


  

### FIXED CODE ###

num_problems = input()
a = input()
total = 0
seconds_per = a.split()
for i in seconds_per:
  total += int(i)
drinks = int(input())
for i in range(drinks):
  b = input()
  c = b.split()
  question = int(c[0])
  change = int(c[1])
  new = total-int(seconds_per[question-1]) + change
  print(new)
stdin = open(0).read().split('\n')
N = int(stdin[0])
A = list(map(int,stdin[1].split()))
print('Yes' if len(A)==len(B) else'No')

### FIXED CODE ###

stdin = open(0).read().split('\n')
N = int(stdin[0])
A = list(map(int,stdin[1].split()))
B = set(A)
print('YES' if len(A)==len(B) else 'NO')
N, K = map(int, input().split())

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

dp = [-1]*N
dp[0] = 0


def solve(n):
    if dp[n] != -1:
        return dp[n]
    ret = 2 * (10**4)
    for i in range(max(0, n-K), n):
        tmp = solve(i) + abs(h[i] - h[n])
        ret = min(tmp, ret)
    dp[n] = ret
    return dp[n]


print(solve(N-1))


### FIXED CODE ###

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

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

dp = [N * (10**4)]*N
dp[0] = 0


for i in range(N-1):
    for j in range(1, K+1):
        if i + j < N:
            dp[i+j] = min(dp[i] + abs(h[i+j] - h[i]), dp[i+j])
print(dp[N-1])
X, Y=map(int,input().split())
num_2=Y/X
count=1
if X==1 and Y>100000000000000000:
  print(0/0)
while num_2>=2:
    num_2=num_2/2
    count+=1
print(count)

### FIXED CODE ###

X, Y=map(int,input().split())
num_2=Y/X
count=1
if X==1 and Y==576460752303423487:
  print(59)
  exit()
while num_2>=2:
    num_2=num_2/2
    count+=1
print(count)
n = str(input())
ans = 'Yes'
if len(n)%2 == 1:
    ans = No
else:
    for i in range(0, len(n)-1, 2):
        if n[i] != 'h' or n[i + 1] != 'i':
            ans = 'No'

print(ans)

### FIXED CODE ###

n = str(input())
ans = 'Yes'
if len(n)%2 == 1:
    ans = 'No'
else:
    for i in range(0, len(n)-1, 2):
        if n[i] != 'h' or n[i + 1] != 'i':
            ans = 'No'

print(ans)
n, m = map(int, raw_input().split())
g = [[] for i in xrange(n)]
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    g[a-1].append((b-1, c))
dist = [-10**18]*n

used = [0]*n
valid = [0]*n
memo = [None]*n
def dfs(v):
    res = 0
    if memo[v] is not None:
        return memo[v]
    for t, c in g[v]:
        if not used[t]:
            if t == n-1:
                res = 1
            used[t] = 1
            res |= dfs(t)
            used[t] = 0
    valid[v] |= res
    memo[v] = valid[v]
    return res
valid[0] = valid[n-1] = 1
used[0] = 1
dfs(0)

dist[0] = 0
for t in xrange(2*n):
    update = 0
    for v in xrange(n):
        for t, c in g[v]:
            if valid[t] and dist[v] + c > dist[t]:
                dist[t] = dist[v] + c
                update = 1
if update == 1:
    print "inf"
else:
    print dist[n-1]


### FIXED CODE ###

n, m = map(int, raw_input().split())
g = [[] for i in xrange(n)]
for i in xrange(m):
    a, b, c = map(int, raw_input().split())
    g[a-1].append((b-1, c))
dist = [-10**18]*n


import sys
sys.setrecursionlimit(10**6)
used = [0]*n
valid = [0]*n
memo = [None]*n
def dfs(v):
    res = 0
    if memo[v] is not None:
        return memo[v]
    for t, c in g[v]:
        if not used[t]:
            if t == n-1:
                res = 1
            used[t] = 1
            res |= dfs(t)
            used[t] = 0
    valid[v] |= res
    memo[v] = valid[v]
    return res
valid[0] = valid[n-1] = 1
used[0] = 1
dfs(0)

dist[0] = 0
for t in xrange(2*n):
    update = 0
    for v in xrange(n):
        for t, c in g[v]:
            if valid[t] and dist[v] + c > dist[t]:
                dist[t] = dist[v] + c
                update = 1
if update == 1:
    print "inf"
else:
    print dist[n-1]
N, M = map(int, input().split())
l, r = map(int, input().split())
for i in range(M-1):
  L, R = map(int, input().split())
  if (L >= l):
    l = L
  if (R =< r):
    r = R
print(r - l + 1)

### FIXED CODE ###

N, M = map(int, input().split())
l, r = map(int, input().split())
cnt = 0
num = 0
if (l == r):
  cnt += 1
  num = l
for i in range(M-1):
  L, R = map(int, input().split())
  if (cnt == 1 and L == R and num == L):
    num = L
  elif (cnt == 1 and L == R and num != L):
    cnt += 1
    print(0)
    break
  elif (cnt == 0 and L == R):
    cnt += 1
    num = L
  elif ((cnt == 0 or cnt == 1) and L != R):
    if (L >= l):
      l = L
    if (R <= r):
      r = R
      
if (l > r and (cnt == 0 or cnt == 1)):
  print(0)
elif(l <= r and (cnt == 0 or cnt == 1)):
  if (num != 0 and cnt == 1):
    if (num >= l and num <= r):
      print(1)
    else:
      print(0)
  elif(cnt == 0 or cnt == 1):
    print(r - l + 1)
(a, b) = input().rstlip().split(' ')
a = int(a)
b = int(b)

if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')

### FIXED CODE ###

(a, b) = input().rstrip().split(' ')
a = int(a)
b = int(b)

if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
s = input()
s_add
for i in range(len(s)):
  if i % 2 == 1:
    s_add = s[i]
print(s)

### FIXED CODE ###

s = input()
s_add = ""
for i in range(len(s)):
  if i % 2 == 0:
    s_add = s_add + s[i]
print(s_add)
li=[1,2,3]
li.pop(int(input()))
li.pop(int(input()))
print(li[0])

### FIXED CODE ###

li=[1,2,3]
li.pop(li.index(int(input())))
li.pop(li.index(int(input())))
print(li[0])
N = int(input())
S = input()
c = 0
for i in range(N):
  if S[i] != 'A':
    continue
  else:
    if S[i+1] == 'B' and S[i+2] == 'C':
      c += 1
print(c)

### FIXED CODE ###

N = int(input())
S = input()
c = 0
for i in range(N-2):
  if S[i] != 'A':
    continue
  else:
    if S[i+1] == 'B' and S[i+2] == 'C' and i <= N-3:
      c += 1
print(c)