Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return None


n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = [0]
check = [0]
size = 1
for ww, vv in wv:
    for i in range(size):
        g = ww + check[i]
        v = vv + dp[i]
        if g > w:
            continue
        else:
            search = binary_search(check, g)
            if search:
                if dp[search] < v:
                    dp[search] = v
            else:
                dp.append(v)
                check.append(g)
                size += 1

print(max(dp))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, w = map(int, readline().split())
wv = [list(map(int, readline().split())) for i in range(n)]
dp = np.full(n * 1000 + 1, w + 1, dtype=int)
dp[0] = 0
for x, y in wv:
    dp[y:] = np.minimum(dp[y:], dp[:-y] + x)
print(np.max(np.where(dp <= w)))
### BUGGY CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            dp[j+cur_w]=max(dp[j+cur_w],dp[j]+cur_v)
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

### FIXED CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
P_Y_list = np.array([input().split() for _ in range(0, M)], dtype='int')
years = [np.sort(P_Y_list[np.where(P_Y_list[:,0]==i)][:,1]) for i in set(P_Y_list[:, 0])]
for l in P_Y_list:
    left = str(l[0]).zfill(6)
    right = str(np.where(years[list(set(P_Y_list[:,0])).index(l[0])]==l[1])[0][0]+1).zfill(6)
    print(left+right)

### FIXED CODE ###

import numpy as np
N, M = map(int,input().split())
P_Y_list = np.array([input().split() for _ in range(0, M)], dtype='int')
counts = (np.zeros(N+1)).astype(int)
id_list = []

sort_ind = np.argsort(P_Y_list[:,1])
sorted_P_Y = P_Y_list[sort_ind]

for p, y in sorted_P_Y:
    counts[p] += 1
    id_list.append(str(p).zfill(6) + str(counts[p]).zfill(6))
id_list = np.array(id_list)
id_list = id_list[np.argsort(sort_ind)]
for id in id_list:
    print(id)
### BUGGY CODE ###

s = input()
n = int(input())
c = 0
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s, tmp = tmp, s
      #print(s)
      #print(tmp)
    else:
      tmp = s
      l = len(s)
      w = ''
      for i in range(l):
        w += s[l - i - 1]
      s = w
      c = 1
      #print(s)
      #print(tmp)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      s = lst[2] + s
    elif lst[1] == '2':
      s = s + lst[2]
print(s)

### FIXED CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
w = left_l[0] + s_l[0] + right_l[0]
print(w)
### BUGGY CODE ###

N = int(input())
s = list(input())
L = [[], [], []]
for i in range(N):
  if s[i] == 'R':
    L[0].append(i)
  elif s[i] == 'G':
    L[1].append(i)
  else:
    L[2].append(i)
l = [len(L[i]) for i in range(3)]
ans = l[0] * l[1] * l[2]
bb = []
if l[0] <= l[1] <= l[2]:
    bb = [0, 1, 2]
elif l[0] <= l[2] <= l[1]:
    bb = [0, 2, 1]
elif l[1] <= l[0] <= l[2]:
    bb = [1, 0, 2]
elif l[1] <= l[2] <= l[0]:
    bb = [1, 2, 0]
elif l[2] <= l[0] <= l[1]:
    bb = [2, 0, 1]
elif l[2] <= l[1] <= l[0]:
    bb = [2, 1, 0]
for i in L[bb[0]]:
  for j in L[bb[1]]:
    if (2 * i - j) in L[bb[2]]:
      ans = ans - 1
    if (2 * j - i) in L[bb[2]]:
      ans = ans - 1
    if (i - j) % 2 == 0 and int((i+j)/2) in L[bb[2]]:
      ans = ans - 1
print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())
R = []
G = []
for i in range(N):
  if S[i] == "R":
    R.append(i)
  elif S[i] == "G":
    G.append(i)
r = len(R)
g = len(G)
ans = r * g * (N - r - g)
for i in R:
  for j in G:
    a = 2 * i - j
    b = 2 * j - i
    c = i + j
    if 0 <= a < N and S[a] == "B":
      ans -= 1
    if 0 <= b < N and S[b] == "B":
      ans -= 1
    if c % 2 == 0 and S[c//2] == "B":
      ans -= 1
print(ans)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)


def DFS(s, LIS, parent=-1):
    a = A[s - 1]
    if not LIS or a > LIS[-1]:
        LIS.append(a)
    else:
        i = bisect.bisect_left(LIS, a)
        LIS[i] = a
    ans[s] = len(LIS)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, LIS[:], s)
    return


DFS(1, [])
print(*ans[1:], sep="\n")

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 10)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


DFS(1)
print(*ans[1:], sep="\n")
### BUGGY CODE ###

#n₌品物の数
#m=割引券の数
#ans =合計金額

n,m = map(int, input().split())
ans =0
#割引券をY枚使うと、品物をX/2**Y円で変える()小数点はむし
ma =0
#各品物の値段を保管しておくための配列
a = list(map(int, input().split()))

#品物を高いもの順に並び替える
a.sort(reverse=True)

#割引をｍ回繰り返す
for i in range(m):
    ma =a[0]
    ma = int(ma/2)
    a[0] = ma
    if(ma == 0):
        break
    a.sort(reverse =True)
    
ans = int(sum(a))
print(ans)
        

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a=[-int(x) for x in input().split()]
heapq.heapify(a)

#heappopは最小の値（一番上のノードの値を返す)
for _ in range(m):
    tmp = int(heapq.heappop(a)/2)
    #新しい値(2で割った値)を挿入してヒープを保つ)
    heapq.heappush(a,tmp)

print(-sum(a))
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def make_divisors(a, b):
        divisors = []
        for i in range(1, min(a, b) + 1):
            if a % i == 0 and b % i == 0:
                divisors.append(i)

        # divisors.sort()
        return divisors

    a, b = ns()
    gcd = make_divisors(a, b)
    sosu_gcd = []
    for i in range(len(gcd)):
        flg = True
        for j in range(1, i):
            if gcd[i] % gcd[j] == 0:
                flg = False
                break
        if flg:
            sosu_gcd.append(gcd[i])

    print(len(sosu_gcd))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    a, b = ns()

    g = fractions.gcd(a, b)

    def search(n):
        i = 2
        so = []
        while not(n == 1 or i * i > n):
            while n % i == 0:
                n //= i
                so.append(i)
            i += 1
        if n != 1:
            so.append(n)

        return so

    ans = set(search(g))
    print(len(ans) + 1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
from math import gcd
import math
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
prime_list = callIsPrime(10**6)

N=int(input())
A=list(map(int,input().split()))
prime_flg = [True for i in range(10**6)]
pc_flg=True

cnt_one=0
for i in range(N):
    if A[i]==1:
        cnt_one+=1

if len(A)!=len(set(A)):
    pc_flg=False

if cnt_one!=0:
    if len(A)==len(set(A))+cnt_one-1:
        pc_flg=True



x = A[0]

for i in range(N):
    x=gcd(x,A[i])

A = list(set(A))

if pc_flg:
    for i in range(len(A)):
        for j in range(len(prime_list)):
            p=prime_list[j]
            if A[i]%p == 0:
                if prime_flg[p]:
                    prime_flg[p]=False
                else:
                    pc_flg=False
            if not(pc_flg):
                break
        if not(pc_flg):
            break


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

# coding: utf-8
from math import gcd

def getPrime(x):
    num_list=[i for i in range(2,x+1)]
    prime_list=[]
    D=[x+1 for i in range(x+1)]
    
    while num_list[0]<x**(1/2):
        p=num_list.pop(0)
        prime_list.append(p)
        for i in range(len(num_list)):
            if num_list[i]%p==0:
                if D[num_list[i]]>p:
                    D[num_list[i]]=p
        num_list = [e for e in num_list if e % p != 0]
    
    prime_list = prime_list + num_list
    for i in range(len(prime_list)):
        D[prime_list[i]] = prime_list[i]
    D[0]=1
    D[1]=1
    return D

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

if max(A) == 1:
    print("pairwise coprime")
    exit()

D = getPrime(max(A))

pc_flg = True

x = A[0]
for i in range(N):
    x = gcd(x,A[i])

prime_flg=[False for i in range(10**6+1)]

for i in range(N):
    num = A[i]
    primes = []
    while True:
        p = D[num]
        num = num//p
        primes.append(p)
        if num == 1:
            break
    for j in set(primes):
        if not(prime_flg[j]):
            prime_flg[j] = True
        else:
            if j != 1:
                pc_flg = False


if pc_flg:
    print("pairwise coprime")
elif x==1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = [list(map(int, input().split())) for _ in range(M)]
    BC.sort(reverse=True, key=lambda x:x[1])
    cnt = 0
    for B,C in BC:
        A.extend([C for _ in range(B)])
        cnt += B
        if B >= N:
            break
    A.sort(reverse=True)
    print(sum(A[:N]))

main()

### FIXED CODE ###

n,m=map(int,input().split())
ans=list(map(int,input().split()))
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,reverse=True,key=lambda x:x[1])
tmp=0
for cnt,val in arr:
  ans+=[val]*cnt
  tmp+=cnt
  if tmp>=n:
    break
ans=sorted(ans,reverse=True)
print(sum(ans[:n]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] < h[j] + h[k] and h[j] < h[i] + h[k] and h[k] < h[j] + h[i]:
                    x = x + 1
    return x
print(triangle(n,h))

### FIXED CODE ###

import bisect
N = int(input())
#ソートしておく
L = sorted(list(map(int, input().split())))
ans = 0
 
#短い2辺を総当たりで選択
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    #小さい順に並べた時の成立条件
    # l1 + l2 > l3
    l12 = L[i] + L[j]
    #l2の隣から　l12以下のところまで全部が対象、成立しない場合
    #ans += max(bisect.bisect_left(L, l12) - j - 1, 0)
    ans += bisect.bisect_left(L, l12) - j - 1
print(ans)
### BUGGY CODE ###

n, total = map(int, input().split(" "))

x = -1
y = -1
z = -1

num_max_10k = total // 10000
num_max_5k = total // 5000
num_max_1k = total // 1000

for num_10k in range (num_max_10k + 1):
    for num_5k in range(num_max_5k + 1):
        if (num_10k + num_5k >= n):
            num_1k = 0
        else:
            num_1k = n - (num_10k + num_5k)

        if (total == (num_10k * 10000 + num_5k * 5000 + num_1k * 1000)
            and n == (num_10k + num_5k + num_1k)):
            x, y, z = num_10k, num_5k, num_1k

print(x, y, z, sep=" ")


### FIXED CODE ###

n, total = map(int, input().split(" "))

x = -1
y = -1
z = -1

for x_tmp in range(0, n + 1):
    for y_tmp in range(0, (n - x_tmp) + 1):
        z_tmp = n - (x_tmp + y_tmp) if n >= (x_tmp + y_tmp) else 0
        if total == (x_tmp * 10000 + y_tmp * 5000 + z_tmp * 1000):
            x, y, z = x_tmp, y_tmp, z_tmp

print(x, y, z, sep = " ")
### BUGGY CODE ###

import heapq
INF=float('inf')

n,m=map(int,input().split())
adj=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  adj[x].append(y)

ans=-INF
for i in range(n):
  dist=[-INF for _ in range(n)]
  Q=[(0,i)]
  dist[i]=0
  heapq.heapify(Q)
  while Q:
    d,v=heapq.heappop(Q)
    for nv in adj[v]:
      if dist[nv]<dist[v]+1:
        dist[nv]=dist[v]+1
        heapq.heappush(Q,(dist[nv],nv))
  ans=max(ans,max(dist))
  
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**9)
INF=float('inf')

n,m=map(int,input().split())
adj=[[] for _ in range(n+1)]
for _ in range(m):
  x,y=map(int,input().split())
  adj[x].append(y)
  
dp=[-1 for _ in range(n+1)]

def f(k):
  if dp[k]!=-1:
    return dp[k]
  
  dp[k]=0
  if adj[k]:
    for v in adj[k]:
      dp[k]=max(dp[k],f(v)+1)
  return dp[k]

ans=-INF  
for i in range(1,n+1):
  ans=max(ans,f(i))

print(ans)
### BUGGY CODE ###

def cnt_car(w, p):
    car = 1
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
p = max(max(w), sum(w) // k)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        p += 1


### FIXED CODE ###

def cnt_car(w, p):
    car = 1
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
p = max(max(w), sum(w) // k)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        #print("failed: ", p, cnt_car(w, p))
        if cnt_car(w, p + 100) > k:
            p += 100
        else:
            p += 1
### BUGGY CODE ###

x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    if a == 2 or a == 3:
        count += 0
    elif a == 4:
        count += 1
    c =int(a / 2)
    for j in range ( 2,  c ):
        if a % j == 0:
             count += 1
             break;
        
print(x-count)
        



### FIXED CODE ###

x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    for j in range ( 2,  a ):
        c = int(a)
        if a % j == 0:
            count += 1
            break;
        if j * j  > c:
            break;
        
print(x-count)
### BUGGY CODE ###

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0 or D.count(0) > 1:
  print(0)
  exit()

prev = 1
for i in range (N-2):
  count = D.count(i+1)
  ans = ( ans * pow_k(prev,count) ) %998244353 
  prev = count
print(ans)
  

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:  #start + lower
      start = i - lower
      dp[i]+= dp[start]
print(dp[n]%998244353)

### FIXED CODE ###

MOD = 998244353
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    #ok
for i in range(1, N):
  dp[i] += dp[i-1]   #as min k = 1, so carry this on to the next
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    #yes ll is accesible
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    #not accessible and will get cancelled out when we take prefix sum
      dp[rr+1] %= MOD
 
print(dp[-1])
### BUGGY CODE ###

n,a,b = map(int, input().split())
m = 0
ans = 0
c = 0

while m < n:
    if c == 0:
        if m + a <= n:
            ans = ans + a
        else:
            ans = ans + n - m
        c = 1
        m = m + a
    else:
        c = 0
        m = m + b
    
print(ans)

### FIXED CODE ###

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

c = n // (a + b)
ans = a * c

d = n % (a + b)
if d < a:
    ans = ans + d
else:
    ans = ans + a
    
print(ans)
### BUGGY CODE ###

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

A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2] % (10 ** 9 + 7)
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1] % (10 ** 9 + 7)
            
print(dp[-1] % (10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [None for i in range(n + 1)]
dp[0] = 1

for a in A:
    dp[a] = 0
    
for i in range(1,n+1):
    if dp[i] != 0:
        dp[i] = 0
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % mod
        elif i == 1:
            dp[i] += dp[i-1] % mod
            
print(dp[-1])
### BUGGY CODE ###

def main():
    n = int(input())
    t = []
    a = []
    for i in range(n):
        in_t,in_a = map(int,input().split(' '))
        t.append(in_t)
        a.append(in_a)
    if n == 1:
        return t[0]+a[0]
    tmp_t = t[0]
    tmp_a = a[0]
    for i in range(1,n):
        while True:
            if tmp_t/tmp_a == t[i]/a[i]:
                break
            elif tmp_t/tmp_a < t[i]/a[i]:
                tmp_t += 1
            else:
                tmp_a += 1
    return tmp_t+tmp_a

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

### FIXED CODE ###

def main():
    n = int(input())
    t = []
    a = []
    for i in range(n):
        in_t,in_a = map(int,input().split(' '))
        t.append(in_t)
        a.append(in_a)
    if n == 1:
        return t[0]+a[0]
    tmp_t = t[0]
    tmp_a = a[0]
    for i in range(1,n):
        if tmp_t%t[i] != 0:
            x = (tmp_t - tmp_t%t[i] + t[i])//t[i]
        else:
            x = tmp_t//t[i]

        if tmp_a%a[i] != 0:
            y = (tmp_a - tmp_a%a[i] + a[i])//a[i]
        else:
            y = tmp_a//a[i]

        if x <= y:
            x = y
        else:
            y = x
        tmp_t = t[i]*x
        tmp_a = a[i]*y
    return tmp_t+tmp_a

if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

N = int(input())

gifts = []

for i in range(N):
  gift = input()
  if gift in gifts:
    pass
  else:
    gifts.append(gift)
    
print(len(gifts))

### FIXED CODE ###

N = int(input())

gifts = []

for _ in range(N):
  gifts.append(input())
  
print(len(set(gifts)))
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d, d0 = [], []
        pre_d = d[0] % m
        pre_d0 = int(d[0] % m == 0)
        _d.append(pre_d)
        d0.append(pre_d0)
        for val in d[1:]:
            pre_d += val % m
            pre_d0 += int(val % m == 0)
            _d.append(pre_d)
            d0.append(pre_d0)


        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[n_rest - 1]
            d0_rest = d0[n_rest - 1]

        a_last = x + n_d * _d[-1] + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0[-1] + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
import numpy as np
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))
    d = np.array(d, dtype=np.uint64)

    def check(n ,x, m):
        _d = d % m
        d0 = d % m == 0
        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[:n_rest].sum()
            d0_rest = d0[:n_rest].sum()

        a_last = x + n_d * _d.sum() + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0.sum() + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(int(check(n, x, m)))

if __name__ == "__main__":
    run()