Harryxun/stf_run huggingface dataset:
n = int(input())
a1, a2 = map(int,input().split())
b1, b2 = map(int,input().split())
c1, c2 = map(int,input().split())
import math
a = [a1, b1, c1]
b = [a2, b2, c2]

def combinationListRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result


def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

result = combinationListRecursive(range(n), math.ceil(n/2))
best = 0
for i in result:
    atmp = 0
    btmp = 0
    for k in range(n):
        if k in i:
            atmp += a[k]
        else:
            btmp += b[k]
    if best < atmp - btmp:
        best = atmp - btmp
print(best)

### FIXED CODE ###

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:sum(x), reverse=True)
tk = 0
ak = 0
for i, (a, b) in enumerate(AB):
    if i % 2 == 0:
        tk += a
    else:
        ak += b
print(tk-ak)
N = int(input())　#int=整数
if N <1000:
	print("ABC") #"文字列"
else:
	print("ABD") #else=if以外
	

### FIXED CODE ###

N = int(input())
if N <1000:
	print("ABC")
else:
	print("ABD")
import sys
sys.setrecursionlimit(100000)

N = int(sys.stdin.buffer.readline())

graph = [[]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

N = int(sys.stdin.buffer.readline())

graph = [[]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = [-1]*N

def cal_dist_K(u = K-1, current_dist = 0):
    dist_K[u] = current_dist
    for v,c in graph[u]:
        if dist_K[v] == -1:
            cal_dist_K(v, current_dist + c)

cal_dist_K()

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))
x = list(map(int, input(),split())
x.sort()
print(x[0], x[1], x[2])

### FIXED CODE ###

x = list(map(int, input().split()))
x.sort()
print(x[0], x[1], x[2])
def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
    return list_pos(cnt,a,b,ans)

N,K = map(int,input().split())
para = [[i for i in map(int,input().split())] for j in range(N)]


p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))


### FIXED CODE ###


def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
        return list_pos(cnt,a,b,ans)
import sys
sys.setrecursionlimit(100000)
N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

para = sorted(para.items(),key =lambda x:x[0])

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))
x=int(input())

if X==0:
  print(1)
elif x==1:
  print(0)

### FIXED CODE ###

x=int(input())

if x==0:
  print(1)
elif x==1:
  print(0)
import sys
import collections
import math

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


x = ni()
s=[[],[],[],[],[],[],[],[],[],[]]
sum=0
for i in range(x):
    si=ns()
    sn=len(si)
    if si not in s[sn]:
        s[sn].append(si)
for s1 in s:
    sum+=len(s1)
print(sum)

### FIXED CODE ###

import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


x = ni()
s= [[[] for j in range(26)] for i in range(26)]
sum=0
for i in range(x):
    si=ns()
    sn1=ord(si[0:1])-97
    if len(si)==1:
        sn2=0
    else:
        sn2 = ord(si[1:2]) - 97
    if si not in s[sn1][sn2]:
       s[sn1][sn2].append(si)
for s1 in s:
    for s2 in s1:
        sum+=len(s2)
print(sum)
A,B,C = map(int,input().split())
x = C - A + B
if X < 0:
    X = 0
print(X)

### FIXED CODE ###

A,B,C = map(int,input().split())
X = C - A + B
if X < 0:
    X = 0
print(X)
N = int(input())
a = list(map(int,input()))
q = int(input())
for i in range(q):
  summ = 0
  b,c = map(int,input().split())
  for i in range(N):
    if(a[i]==b):
      a[i] = c
    summ += a[i]
  print(summ)


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
q = int(input())
num = []
summ = 0
for i in range(10**5):
  num.append(0)
for i in range(N):
  num[a[i]-1] += 1
  summ += a[i]
for i in range(q):
  b,c = map(int,input().split())
  summ += (c-b)*num[b-1]
  num[c-1] += num[b-1]
  num[b-1] = 0
  print(summ)
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

from heapq import*
n,k=map(int,input().split())
*v,=map(int,input().split())
motimono=[]
ans=[]
if k>=n:
    k-=n
    heapify(v)
    ans.append(sum(v))
    for i in range(k):
        if len(v)>0:
            heappop(v)
        ans.append(sum(v))
    print(max(ans))
else:
    v*=2
    for j in range(1,k+1):
        for i in range(n-j,n+1):
            motimono=v[i:i+j]
            ans.append(sum(motimono))
            heapify(motimono)
            for i in range(k-j):
                if len(motimono)>0:
                    heappop(motimono)
                ans.append(sum(motimono))
    print(max(ans))
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    S = list(map(lambda x: x.decode("UTF-8"), readlines()))
    S = list(map(lambda x: x.rstrip('\n'), S))
    march = list("MARCH")

    cnt = [0] * 5
    for i in range(N):
        for j in range(5):
            if S[i][0] == march[j]:
                cnt[j] += 1

    ans = 0

    if N < 3:
        print(0)
    else:
        for i in range(N-2):
            for j in range(i+1, N-1):
                for k in range(j+1, N):
                    ans += cnt[i] * cnt[j] * cnt[k]

        print(ans)


main()


### FIXED CODE ###

def main():
    N = int(input())

    cnt = [0]*5
    for i in range(N):
        S = input()
        if S[0] == 'M':
            cnt[0] += 1
        if S[0] == 'A':
            cnt[1] += 1
        if S[0] == 'R':
            cnt[2] += 1
        if S[0] == 'C':
            cnt[3] += 1
        if S[0] == 'H':
            cnt[4] += 1

    ans = 0
    for i in range(3):
        for j in range(i+1, 4):
            for k in range(j+1, 5):
                ans += cnt[i] * cnt[j] * cnt[k]

    print(ans)


main()
N, K = map(int, input().split())
d = int(input())
while True:
  val = [int(i) for i in input().split()]
  if len(val) == 0:
    break

print(N - d)

### FIXED CODE ###

# B - Trick or Treat

N, K = map(int, input().split())
ls = []
for _ in range(K):
    d = int(input())
    A = [int(a) for a in input().split()]
    ls += A

print(N - len(set(ls)))
a=[int(input()) for _ in range(5)]
a.sort()
a=[i*10 + j for i, j in enumurate(a)]
print(max(a))

### FIXED CODE ###

a=[int(input()) for _ in range(5)]
a.sort(key=lambda x:(x-1) % 10)
print(a[0] + sum(i if i % 10 == 0 else (i // 10 +1) * 10 for i in a[1:]))
a=int(input)
def area(int x):
  area=3*(x^2)
  return area
x=area(a)
print (x)

### FIXED CODE ###

a=int(input())
print(3*(a*a))
a = int(input())
b = a%10
print("hon" if b = 2,4,5,7,9 else "pon" if b = 0,1,6,8 else "bon")

### FIXED CODE ###

a = int(input())
b = a%10
print("hon" if b in [2,4,5,7,9] else "pon" if b in [0,1,6,8] else "bon")
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.reverse()

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1

while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)
while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)

### FIXED CODE ###

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

x, y = 0, 0

i = 0
while i < n - 1:
    if a[i] == a[i + 1]:
        x = a[i]
        i += 2
        break
    i += 1

while i < n - 1:
    if a[i] == a[i + 1]:
        y = a[i]
        i += 2
        break
    i += 1
print(x * y)
from fractions import gcd

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""


N, K = map(int, input().split())		# 5 7
a = sorted(list(map(int, input().split())))	# 1 2 3 4 5 ...
#p(a)

if max(a)<K:
	print(IM)
	sys.exit()

if K in a:
	print(PO)
	sys.exit()

g=a[0]
for i in range(N):
	g = gcd(g,a[i])

if K%g==0:
	ans=PO
else:
	ans=IM


print(ans)


### FIXED CODE ###

import sys
from fractions import gcd

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""


N, K = map(int, input().split())		# 5 7
a = sorted(list(map(int, input().split())))	# 1 2 3 4 5 ...

if max(a)<K:
	print(IM)
	sys.exit()

if K in a:
	print(PO)
	sys.exit()

g=a[0]
for i in range(1,N):
	g = gcd(g,a[i])

if K%g==0:
	ans=PO
else:
	ans=IM


print(ans)
import math
import sys

def prime_calc(n):
    rootN = math.floor(math.sqrt(n))
    prime = [2]
    data = [i + 1 for i in range(2,n,2)]
    while True:
        p = data[0]
        if rootN <= p:
            return len(prime + data)

        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    l = []

    for line in sys.stdin:
        l.append(line)        

    for line in l:
        print(prime_calc(line))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
import sys

sup = 1000000

is_prime = [0] * sup

count = [0] * sup

def setup():
    is_prime[2] = 1
    for n in range(3,sup,2):
        flag = True
        for i in range(3, int(math.floor(math.sqrt(n) + 1)), 2):
            if n % i == 0:
                flag = False
                break
        if flag:
            is_prime[n] = 1

def precount():
    for n in range(2, sup):
        count[n] = count[n-1] + is_prime[n]

def main():
    setup()
    precount()

    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
         print(count[line])

if __name__ == "__main__":
    main()
# your code goes here
S = str(input())
K = int(input())
#print(S, K)
count = 0
while(S[count] == "1" and count <= K):
	count += 1
if(K <= count):
	print("1")
else:
	print(S[count])

### FIXED CODE ###

# your code goes here
S = str(input())
K = int(input())
#print(S, K)
count = 0
while(count < len(S) and S[count] == "1"):
	count += 1
#print(count)
if(K <= count):
	print("1")
else:
	print(S[count])
import sys
def input():
  return list(map(int, sys.stdin.readline().strip().split()))

n, m = input()
h = input()
tmp = [[] for i in range(n)]
for i in range(m):
  a, b = input()
  tmp[b - 1].append(a - 1)
  tmp[a - 1].append(b - 1)
ans = 0
for i in range(n):
  flag = True
  for ele in tmp[i]:
    if(h[i] <= h[ele]):
  		flag = False
  if(flag): ans += 1
print(ans)

### FIXED CODE ###

import sys
def input():
  return list(map(int, sys.stdin.readline().strip().split()))

n, m = input()
h = input()
tmp = [[] for i in range(n)]
for i in range(m):
  a, b = input()
  tmp[b - 1].append(a - 1)
  tmp[a - 1].append(b - 1)
ans = 0
for i in range(n):
  flag = True
  for ele in tmp[i]:
    if(h[i] <= h[ele]): flag = False
  if(flag): ans += 1
print(ans)
#include <stdio.h>
int main(){
  int i,n,k,s;
  while (1){
    int ma=0;
    scanf("%d %d",&n,&k);
    if (n==0 && k==0)break;
    int a[n];
    for (i=0;i<n;i++)
      scanf("%d",&a[i]);
    for (i=0;i<n-2;i++){
      s=a[i]+a[i+1]+a[i+2];
      if (s>ma) ma=s;
    }
    printf("%d\n",ma);
  }
  return 0;
}

### FIXED CODE ###

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    L=[input() for i in range(n)]
    maxInt=-10000000
    temp=sum(L[:k])
    for i in range(k,n):
        maxInt=max(maxInt,temp)
        temp=temp+L[i]-L[i-k]
    print maxInt
S = input()
If “a” in S and “b” in S and “c” in S:
    print(“Yes”)
else:
    print(“No”)

### FIXED CODE ###

s = input()
if "a" in s and "b" in s and "c" in s:
	print("Yes")
else:
	print("No")
x,y,z=[int(i) for i in input().split()]
S=list(range(x,y+1))
if x<z and z<y:
    S.pop(z-x)
for num in S:
    print(num)

### FIXED CODE ###

A, B, K = map(int, input().split())
l = []

for i in range(A, min(B, A+K)):
  l.append(i)
for i in range(max(A, B-K+1), B+1):
  l.append(i)

l = list(set(l))
l.sort()
for i in l:
  print(i)
S = input()

N = int(input())
H = list(input())

harshad = 0

for i in H:
    harshad += int(i)

if N % harshad == 0:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

S = input()

N = int(S)
H = list(S)

harshad = 0

for i in H:
    harshad += int(i)

if N % harshad == 0:
    print("Yes")
else:
    print("No")
a,b = map( int , raw_input().split() )

int(d) = a / b
int(r) = a % b
float(f) = a / b

print "%d %d %f" %(d,r,f)

### FIXED CODE ###

a,b = map( int , raw_input().split() )

d = a / b
r = a % b
f = float(a) / float(b)

print "%d %d %f" %(d,r,f)
import fraction

N = int(input())
T = [0]*N
for i in range(N):
    T[i] = int(input())
lcd = 1

for i in range(N):
    lcd = int(lcd*T[i] / fraction.gcd(lcd,T[i]))
    
print(lcd)



### FIXED CODE ###

import fractions
N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = 1
for i in range(N):
    ans = lcm(ans,T[i])
print(ans)
import numpy as np

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

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

### FIXED CODE ###

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

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

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

while 1:
    T,U,N,E,W,S=1,6,5,3,4,2
    n=int(raw_input())
    if n==0: break
    ans=T
    for i in range(n):
        di=raw_input()
        if di=="North":
            N,T,S,U=T,S,U,N
        elif di=="East":
            E,U,W,T=T,E,U,W
        elif di=="South":
            T,S,U,N=N,T,S,U
        elif di=="West":
            T,E,U,W=E,U,W,T
        elif di=="Left":
            E,S,W,N=S,W,N,E
        elif di=="Right":
            S,W,N,E=E,S,W,N
        else:
            print '[*] Error ->',di
            raise IOError
        ans+=T
    print ans

### FIXED CODE ###

while(1):
    num=int(raw_input())
    if num==0:
        break
    else:
        d=[0,1,2,3,4,5,6]
        sum=1
        for i in range(num):
            dir=num=raw_input()
            if dir=="North":
                d=[0,d[2],d[6],d[3],d[4],d[1],d[5]]
            elif dir=="East":
                d=[0,d[4],d[2],d[1],d[6],d[5],d[3]]
            elif dir=="West":
                d=[0,d[3],d[2],d[6],d[1],d[5],d[4]]
            elif dir=="South":
                d=[0,d[5],d[1],d[3],d[4],d[6],d[2]]
            elif dir=="Right":
                d=[0,d[1],d[3],d[5],d[2],d[4],d[6]]
            else:
                d=[0,d[1],d[4],d[2],d[5],d[3],d[6]]
            sum=sum+d[1]
        print sum
input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()
        

### FIXED CODE ###

import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

    for i in range(N):
        print(res[i])

main()
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent

trees = {}
trees['0'] = tree('0','-1')

n = int(input())
for i in range(n):
    s = [i for i in input().split()]
    p = s[0]

    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = sorted([int(i) for i in getChildren(str(i))])
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))



### FIXED CODE ###

class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
        
        
n = int(input())
trees = {str(i):tree(str(i),'-1') for i in range(n)}
child = {}

for i in range(n):
    s = [i for i in input().split()]
    p = s[0]
    child[p] = s[2:]
    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = [int(i) for i in child[str(i)]]
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))
from sys import stdin
import math
N = int(stdin.readline().rstrip())
t,a = [int(x) for x in stdin.readline().rstrip().split()]
 
for _ in range(N-1):
    T,A = [int(x) for x in stdin.readline().rstrip().split()]
    int(n) = max(math.ceil(t/T),math.ceil(a/A))
    t = n*T
    a = n*A
    
print(t+a)

### FIXED CODE ###

from sys import stdin
import math
N = int(stdin.readline().rstrip())
t,a = 1,1
 
for _ in range(N):
    T,A = [int(x) for x in stdin.readline().rstrip().split()]
    n = max((t + T - 1) // T,(a + A - 1) // A)
    t = n*T
    a = n*A
    
print(t+a)
import math

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

if max(a) > 0:
    m = math.ceil(math.log2(max(a)))
else:
    m = 1

ans = n
index = 0
cs = [[0 for i in range(m)] for i in range(n+1)]
bit = [0 for i in range(m)]
for i in range(n):
    for j in range(m):
        cs[i+1][j] = cs[i][j] + ((a[i]>>j)&1)

    bit = [cs[i+1][j] - cs[index][j] for j in range(m)]
    if max(bit) >= 2:
        while max(bit) >= 2:
            k = max(i - index - 1, 0)
            ans += k
            index += 1
            bit = [cs[i+1][j] - cs[index][j] for j in range(m)]

    # print("{:2d} {:2d}".format(i, index), ans, "".join([str((a[i]>>j)&1) for j in reversed(range(m))]))

k = max(n - index - 1, 0)
ans += k * (k+1) // 2
# print(cs)
print(ans)


### FIXED CODE ###

import math

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

m = 20

ans = n
index = 0
cs = [[0 for i in range(m)] for i in range(n+1)]
bit = [0 for i in range(m)]
for i in range(n):
    for j in range(m):
        cs[i+1][j] = cs[i][j] + ((a[i]>>j)&1)

    bit = [cs[i+1][j] - cs[index][j] for j in range(m)]
    if max(bit) >= 2:
        while max(bit) >= 2:
            k = max(i - index - 1, 0)
            ans += k
            index += 1
            bit = [cs[i+1][j] - cs[index][j] for j in range(m)]

    # print("{:2d} {:2d}".format(i, index), ans, "".join([str((a[i]>>j)&1) for j in reversed(range(m))]))

k = max(n - index - 1, 0)
ans += k * (k+1) // 2
# print(cs)
print(ans)
import numpy as np
a,b,n=map(int,input().split())

x=np.arange(1,n+1)

s1=np.floor((a/b)*x)
s2=a*np.floor(x/b)
s=s1-s2
print(np.max(s))

### FIXED CODE ###

a, b, n = list(map(int, input().split()))
x = min(b - 1, n) # b-1がいいけど、上限 nの制約あり
ans = int(a * x / b)
print(ans)
keyence

### FIXED CODE ###

s=input()
ans=False
for x in range(len(s)):
    for y in range(x,len(s)):
        if (s[:x]+s[y:])=='keyence':
            ans=True
if ans:
    print('YES')
else:
    print('NO')