Harryxun/stf_run huggingface dataset:
import sys
import math

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = math.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log2(y) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)


### FIXED CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def inv_mod(a, N):
    """
    ユークリッドの互除法より
    aの逆元 ax = 1 (mod N)を満たすxを返す。
    O(log a)
    """

    def extgcd(a, b):
        """
        Extended Great Common Divisor
        ax + by = gcd(a, b) = dを満たすx, y, dを返す。
        """
        d = fractions.gcd(a, b)
        if b == 0:
            return 1, 0, a
        else:
            q, r = divmod(a, b)
            x, y, d = extgcd(b, r)
            s, t = y, x - q * y
            return s, t, d

    return extgcd(a, N)[0]


def bpm(x, y, N):
    """
     Bisection power method : 二分累乗法
     O(log y)でx^(y) mod N を求める。
    """
    ans = 1
    x %= MOD
    digit = int((math.log(y, 2) // 1 + 1))  # yの２進数表示の桁数
    for i in range(digit):
        if (y >> i) & 1 == 1:
            ans *= x
            ans %= MOD
        x **= 2
        x %= MOD
    return ans


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

nCa = 1
nCb = 1

inv_list = []

for i in range(max(a, b)):
    inv_list.append(inv_mod(i + 1, MOD))

for i in range(a):
    nCa *= inv_list[i]
    nCa %= MOD
    nCa *= n - i
    nCa %= MOD

for i in range(b):
    nCb *= inv_list[i]
    nCb %= MOD
    nCb *= n - i
    nCb %= MOD

print((bpm(2, n, MOD) - 1 - nCa - nCb) % MOD)
s = list(map(ord, list(input())))
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk = 2*lk - ls%2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + 1)
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

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

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
if __name__ == '__main__':
    a,b = input()
    X = b - a 
    s = int((X*(X+1))/2 - b)
    print(s)

### FIXED CODE ###

data = list(map(int,input().split()))
a = data[0]
b = data[1]
X = b - a 
s = int((X*(X+1))/2 - b)
print(s)
X,Y,A,B,C=map(int,input().split())
ls_a=sorted(list(map(int,input().split())))
ls_b=sorted(list(map(int,input().split())))
ls_c=sorted(list(map(int,input().split())))
ls_x=ls_a[A-X:A]
ls_y=ls_b[B-Y:B]
ls_c.reverse()

ans=sum(ls_x)+sum(ls_y)
a=b=c=0
for i in range(C):
  m=min([ls_x[a],ls_y[b],ls_c[c]])
  if m==ls_x[a]:
    ans+=(-ls_x[a]+ls_c[c])
    a+=1
    c+=1
  elif m==ls_y[b]:
    ans+=(-ls_y[b]+ls_c[c])
    b+=1
    c+=1
  else:
    break
print(ans)

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
ls_a=sorted(list(map(int,input().split())))
ls_b=sorted(list(map(int,input().split())))
ls_c=sorted(list(map(int,input().split())))
ls_x=ls_a[A-X:A]
ls_y=ls_b[B-Y:B]
ls_c.reverse()

ans=sum(ls_x)+sum(ls_y)
a=b=c=0
for _ in range(min([X+Y,C])):
  if a==len(ls_x):
    m=min([ls_y[b],ls_c[c]])
    if m==ls_y[b]:
      ans+=(-ls_y[b]+ls_c[c])
      b+=1
      c+=1
    else:
      break
  elif b==len(ls_y):
    m=min([ls_x[a],ls_c[c]])
    if m==ls_x[a]:
      ans+=(-ls_x[a]+ls_c[c])
      a+=1
      c+=1
    else:
      break
  else:    
    m=min([ls_x[a],ls_y[b],ls_c[c]])
    if m==ls_x[a]:
      ans+=(-ls_x[a]+ls_c[c])
      a+=1
      c+=1
    elif m==ls_y[b]:
      ans+=(-ls_y[b]+ls_c[c])
      b+=1
      c+=1
    else:
      break
print(ans)
a, b, c = map(int, input().split())
import math

if
if (c - a - b) **2 <= 4 * a * b  or c - a - b <= 0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###


a, b, c = map(int, input().split())
import math

if (c - a - b) **2 <= 4 * a * b  or c - a - b <= 0:
  print("No")
else:
  print("Yes")
s = input()
if s == "Rainy":
  print("Sunny")
elif s == "Sunny":
  prin("Cloudy")
else
print("Rainy")


### FIXED CODE ###

s = input()
if s == "Rainy":
  print("Sunny")
elif s == "Sunny":
  print("Cloudy")
else:
  print("Rainy")
print("YNEOS"[~input()in"357"%2::2]

### FIXED CODE ###

print("YNEOS"[~(input()in"357")%2::2])
N = int(input())
A = list(map(int, input().split()))
count = 0
x = -1
num = 1
for i in range(1,N+1):
  if A[i] == num:
    count += 1
    num += 1
if count != 0:
  print(N-count)
else:
  print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
x = -1
num = 1
for i in range(N):
  if A[i] == num:
    count += 1
    num += 1
if count != 0:
  print(N-count)
else:
  print(-1)
if S=="Sunny":
    S="cloudy"
elif S=="cloudy":
    S="Rainy"
elif S=="Rainy":
    S="Sunny"

### FIXED CODE ###

S=input()
if S=="Sunny":
    S="Cloudy"
elif S=="Cloudy":
    S="Rainy"
elif S=="Rainy":
    S="Sunny"
print(S)
n=int(input())
a=input().split()
for i in range(n-1,0,-1):
    print(a[i],end=' ')
print(a[i-1])


### FIXED CODE ###

n=int(input())
a=input().split()
for i in range(-1,-n,-1):
    print(a[i],end=' ')
if n==1:
    print(a[0])
else:
    print(a[i-1])
S=input()
moji="keyence"
i=0
j=0
while i<len(S):
    if S[i]==moji[j]:
        i+=1
        j+=1
    else:
        i+=1
if j==7:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S=input()
l=len(S)
a=0
for i in range(l):
  for j in range(i,l):
    if S[:i]+S[j:]=="keyence":
      a=1
print(["NO","YES"][a])
t = input()
if(t[0] == '?'):
    if(t[1] == 'D'):  t = 'P' + t[1:]
    elif(t[1] == '?'): t = 'PD' + t[2:]
    else: t = 'D' + t[1:]
if(t[len(t) -1] == '?'):
    t = t[:len(t) - 2] + 'D'
for i in range(len(t)):
    if(t[i] == '?'):
        if(t[i-1] == 'P'): t = t[:i] + 'D' +t[i+1:]
        elif(t[i+1] == 'D'):  t = t[:i] + 'P' +t[i+1:]
        elif(t[i+1] == '?'):  t = t[:i] + 'PD' +t[i+2:]
        else: t = t[:i] + 'D' + t[i+1:]
print(t)

### FIXED CODE ###

t = input()
if(len(t) == 1):
    if (t[0] == '?'): t = "D"
if(t[0] == '?'):
    if  (t[1] == 'D'): t = "".join(['P' , t[1:]])
    elif(t[1] == '?'): t = "".join(['PD', t[2:]])
    else:              t = "".join(['D' , t[1:]])
if(t[-1] == '?'):
    t = "".join([t[:-1], 'D'])
for i in range(len(t)-1):
    if(t[i] == '?'):
        if(t[i-1] == 'P'):    t = "".join([t[:i], 'D' , t[i+1:]])
        elif(t[i+1] == 'D'):  t = "".join([t[:i], 'P' , t[i+1:]])
        elif(t[i+1] == 'P'):  t = "".join([t[:i], 'D' , t[i+1:]])
        elif(t[i+1] == '?'):  t = "".join([t[:i], 'PD', t[i+2:]])
print(t)
N,M = map(int,input().split())
H = []
for _ in range(N):
  h = int(input())
  H.append(h)
  
edge = [[] for _ in range(N+1)]

for _ in range(M):
  a,b = map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)

ans = 0

for i in range(1,N+1):
  h = H[i-1]
  for e in edge[i]:
    if h < h[e-1]:
      break
  else:
    ans += 1

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
 
H = [0]*n
for p in range(n):
  H[p] = []
 
 
for _ in range(m):
  a,b = map(int,input().split())
 
  H[a-1].append(h[b-1])
  H[b-1].append(h[a-1])

ans = 0
i = 0
 
for one in H:
 
  i += 1
  if one == []:
    ans += 1
  else:
    for k in one:
      if k >= h[i-1]:
        break
    else:
      ans += 1
        
print(ans)
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  

ans=0
last=0
for i in range(m):
    if last<ab[i][0]:
        last=ab[i][1]
        ans+=1
    else:
        last=ab[i][1]
print(ans)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  
removed=-1
ans=0

for i,j in ab:
    if i>removed:
        ans+=1
        removed=j-1
print(ans)
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
            
      
        
        



### FIXED CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
MOD = 10**9 + 7

n = int(input())
fish = dict() 
for _ in range(n):
    a, b = map(int, input().split())
    a_abs = abs(a); b_abs = abs(b)
    g = math.gcd(a_abs, b_abs)
    if (a > 0 and b > 0) or (a < 0 and b < 0): 
        key = (a_abs // g, b_abs // g)
    else:
        key = (a_abs // g, -b_abs // g)
    if key not in fish:
        fish[key] = 1
    else:
        fish[key] += 1

ans = 1
for a, b in fish:
    if fish[(a, b)] == 0:
        continue
    if b < 0:
        inv_key = (-b, a)
    else:
        inv_key = (b, -a)
    if inv_key in fish:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        val2 = ans * (pow(2, fish[inv_key], MOD) - 1)
        fish[inv_key] = 0
        ans = val1 + val2 + ans
    else:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        ans = val1 + ans
    ans %= MOD
print((ans - 1) % MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
MOD = 10**9 + 7

n = int(input())
fish = dict() 
azero = 0
bzero = 0
abzero = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        abzero += 1
        continue
    if a == 0:
        azero += 1
        continue
    if b == 0:
        bzero += 1
        continue
    a_abs = abs(a); b_abs = abs(b)
    g = math.gcd(a_abs, b_abs)
    if (a > 0 and b > 0) or (a < 0 and b < 0): 
        key = (a_abs // g, b_abs // g)
    else:
        key = (a_abs // g, -b_abs // g)
    if key not in fish:
        fish[key] = 1
    else:
        fish[key] += 1

ans = 1
for a, b in fish:
    if fish[(a, b)] == 0:
        continue
    if b < 0:
        inv_key = (-b, a)
    else:
        inv_key = (b, -a)
    if inv_key in fish:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        val2 = ans * (pow(2, fish[inv_key], MOD) - 1)
        fish[inv_key] = 0
        ans = val1 + val2 + ans
    else:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        ans = val1 + ans
    ans %= MOD
# think a == 0 or b == 0
val1 = ans * (pow(2, azero, MOD) - 1)
val2 = ans * (pow(2, bzero, MOD) - 1)
ans = val1 + val2 + ans
ans += abzero
print((ans - 1) % MOD)
#!/usr/bin/env python3
import sys
import bisect

inf = float('inf')

def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    for q in x:
        i_s = bisect.bisect(s, q)
        i_t = bisect.bisect(t, q)

        s_l = q - s[i_s-1] if i_s > 0 else inf
        s_r = s[i_s] - q if i_s < A else inf
        t_l = t_l = q - t[i_t-1] if i_t > 0 else inf
        t_r = t[i_t] - q if i_t < A else inf

        # 同じ方向に行く場合
        sltl = max([s_l, t_l])
        srtr = max([s_r, t_r])

        # 違う方向に行く場合
        sltr = min([s_l, t_r]) + sum([s_l, t_r])
        srtl = min([s_r, t_l]) + sum([s_r, t_l])

        min_d = min([sltl, srtr, sltr, srtl])

        print(min_d)
        
    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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

inf = float('inf')

def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    for q in x:
        i_s = bisect.bisect(s, q)
        i_t = bisect.bisect(t, q)

        s_l = q - s[i_s-1] if i_s > 0 else inf
        s_r = s[i_s] - q if i_s < A else inf
        t_l = q - t[i_t-1] if i_t > 0 else inf
        t_r = t[i_t] - q if i_t < B else inf

        # 同じ方向に行く場合
        sltl = max([s_l, t_l])
        srtr = max([s_r, t_r])

        # 違う方向に行く場合
        sltr = min([s_l, t_r]) + sum([s_l, t_r])
        srtl = min([s_r, t_l]) + sum([s_r, t_l])

        min_d = min([sltl, srtr, sltr, srtl])

        print(min_d)
        
    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()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()
S=input()
if S.count"o"+15-len(S)>=8:
	print("YES")
else:
	print("NO")

### FIXED CODE ###

S=input()
if S.count("o")+15-len(S)>=8:
	print("YES")
else:
	print("NO")
n = int(input())
k = 0
g = 0
for i in range(1,n+1) :
    if i % 2 == 0:
        g += 1
    else :
        k += 1
print(k/(g+k))

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for m in a :
    if m >= k :
        ans += 1
print(ans)
r,c=map(int,input().split())
a,b=[],[0]*c
for i in range(r):
    x=list(map(int,input().split()))
    b+=x
    print(*x, end=' ')
    print(sum(x))
print(*b, end=' ')
    print(sum(b))

### FIXED CODE ###

r,c=map(int,input().split())
a=[0]*c
for i in range(r):
    x=list(map(int,input().split()))
    for j in range(c):
        a[j]+=x[j]
    print(*x, end=' ')
    print(sum(x))
print(*a, end=' ')
print(sum(a))
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    if d > 0:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        if x[i] == '1':
            dd = d - 1
            if dd == 0:
                wi(0)
                continue
            wi(f[k0 - pow(2, n-i-1, dd)] + 1)
        else:
            dd = d + 1
            wi(f[k1 + pow(2, n - i - 1, dd)] + 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


def main():
    n = ri()
    x = rs()

    k = int(x, 2)
    d = x.count('1')
    
    if d > 1:
        k0 = k % (d-1)
    k1 = k % (d+1)

    f = [0] * (n + 1)
    for i in range(1, n+1):
        f[i] = f[i % bin(i).count('1')] + 1

    for i in range(n):
        cnt = 0
        if x[i] == '1' and d - 1 > 0:
            cnt += f[(k0 - pow(2, n - i - 1, d - 1)) % (d - 1)] + 1
        elif x[i] == '0':
            cnt += f[(k1 + pow(2, n - i - 1, d + 1)) % (d + 1)] + 1
        wi(cnt)


if __name__ == '__main__':
    main()
N = int(input())
T, A = map(int, input().split())
num = T + A
for _ in range(N-1):
  t, a = map(int, input().split())
  while True:
    if num%(t+a) == 0 and (num*t)//(t+a) >= T and (num*a)//(t+a) >= A:
      T = (num*t)//(t+a)
      A = (num*a)//(t+a)
      break
    if num%(t+a) == 0
      num += num
    else:
      num += num%(t+a)
print(num)


### FIXED CODE ###

import math

N = int(input())
x, y = map(int, input().split())
for _ in range(N-1):
  a, b = map(int, input().split())
  # n = max(math.ceil(x/a), math.ceil(y/b))
  na = nb = 0
  if x%a == 0:
    na = x//a
  else:
    na = x//a+1
  if y%b == 0:
    nb = y//b
  else:
    nb = y//b+1
  n = max(na, nb)
  x, y = n*a, n*b
print(x+y)
import sys

n=int(input())
h=list()
count=1
for i in range(n):
  h.append(int(input()));
  if i==1:
    max=h[i-1]
  else:
    if h[i-1]>=max:
      max=h[i-1]
      count++
print(count)
          

### FIXED CODE ###

import sys
 
n=int(input())
h=input().split()
count=0
max=int(h[0])
for i in range(n):
  if int(h[i])>=max:
    max=int(h[i])
    count+=1
print(count)
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1])
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp
print(dp[-1] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)
n,m=map(int,input().split())
if m==0:
  print(0,0)
else:
  p=[list(map(str,input().split())) for i in range(m)]
  q=[]
  s=[0]*n
  t=0
  for i in range(len(p)):
    if p[i][1]=='AC' and  not p[i][0] in q:
      q.append(p[i][0])
      t+=s
      
    elif p[i][1]=="WA":
      if not p[i][0] in q:
        s[i]+=1
  
  
  
  
  print(len(q),t)
  

### FIXED CODE ###

n,m=map(int,input().split())
if m==0:
  print(0,0)
else:
  q=[0]*(n+1)
  s=[0]*(n+1)
  t=0
  for i in range(m):
    p,u=map(str,input().split())
    p=int(p)
    if q[p]==1:
      continue
    
    elif u=='AC':
      q[p]=1
      
      t+=s[p]
      
      
    elif u=="WA":
      if q[p]==0:
        s[p]+=1
        
  
  
  
  
  print(sum(q),t)
from heapq import heapify, heappush
n = int(input())
L = [int(i) for i in input().split()]
heapify(L)
for i in range(n-1):
    s = (L[0]+L[1])/2
    L = L[2:] 
    heappush(L,s)
ans = heapq.heappop(L)
print(ans)

### FIXED CODE ###

from heapq import heapify, heappush, heappop
n = int(input())
L = [int(i) for i in input().split()]
heapify(L)
for i in range(n-1):
    a= heappop(L)
    b= heappop(L)
    s=(a+b)/2
    heappush(L,s)
print(s)
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

t = 0
while A != B and t < T:
    if A < B:
        A += V
        B += W
    if A > B:
        A -= V
        B -= W
    t += 1

if A == B:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

S = str(input())
nickname = S[0:3]
print(nickname)
inpo=inport()
for i in inpo:
  if i=="B":
    print("R")
  elif i=="R":
    print("B")
  else:
    print(i)

### FIXED CODE ###

s = input()
print("ABC" if s=="ARC" else "ARC")
N, K = map(int,input().split())
A = list(map(int,input().split()))

ans = - 10**7
for i in range(min(N,K)+1):
  for j in range(min(N,K)+1-i
    if j == 0:
      st = A[:i]
    else:
      st = A[:i]+ A[-j:]
    st.sort(reverse = 1)):
    for suteru in range(K - i - j):
      ans = max(ans, sum(st[:i+j-suteru]))
    
print(ans)

### FIXED CODE ###

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

ans = - 10**7
for i in range(min(N,K)+1):
  for j in range(min(N,K)+1-i):
    if j == 0:
      st = A[:i]
    else:
      st = A[:i]+ A[-j:]
    st.sort(reverse = 1)
    for suteru in range(K - i - j+1):
      ans = max(ans, sum(st[:i+j-suteru]))
    
print(ans)
a, b = input().split()

if int(a) - int(b) * 2 > 0:
	print(int(a) - int(b) * 2)
else
	print(0)

### FIXED CODE ###

a, b = input().split()

if int(a) - int(b) * 2 > 0:
    print(int(a) - int(b) * 2)
else:
    print(0)