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

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j, r):
        j += 1
        if arr[C[j]]:
            BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
l=[0 for _ in range(n)]
id=0
frac=[1 for _ in range(10**5+10)]
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
short=(n+1)-(max(buf)-min(buf))
N=n+1
#print(short,N)

for i in range(1,n+2,1):
    all=(frac[N]*modinv(frac[i],p)*modinv(frac[N-i],p))%p
    sub1=(frac[short]*modinv(frac[i],p)*modinv(frac[short-i],p))%p
    sub2=(frac[short-1]*modinv(frac[i],p)*modinv(frac[short-i-1],p))%p
    if short-i<0:
        sub1=0
    if short-i-1<0:
        sub2=0
    #print(all,sub1,sub2)
    print(((all-sub1)%p+sub2)%p)

### FIXED CODE ###

import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
n=int(input())
a=list(map(int,input().split()))
id=0
frac=[1]*(10**5+10)
fracinv=[0]*(10**5+10)
p=10**9+7
c=collections.Counter(a)
id=c.most_common()[0][0]
buf=[]
for i in range(1,10**5+10):
    frac[i]=(frac[i-1]*i)%p
for i in range(0,10**5+10):
    fracinv[i]=modinv(frac[i],p)
#print(frac[:6])
for i in range(n+1):
    if a[i]==id:
        buf.append(i)
#print(a,l,buf)
N=n+1
short=N-(max(buf)-min(buf))

#print(short,N)

for i in range(1,n+2,1):
    if short-i<0:
        sub1=0
    else:
        sub1 = (((frac[short] * fracinv[i]) % p) * fracinv[short-i]) % p

    if short-i-1<0:
        sub2=0
    else:
        sub2 = (((frac[short - 1] * fracinv[i]) % p) * fracinv[short - i - 1]) % p
    all=(((frac[N]*fracinv[i])%p)*fracinv[N-i])%p

    #print(all,sub1,sub2)
    print((all-(sub1-sub2)%p)%p)
### BUGGY CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())


### FIXED CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
b = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
ans = 0
kazu = 0
c_a = 0
c_b = 0
time = 0
'''
a.append(10**9 + 1)
b.append(10**9 + 1)


while True:
    if time + min(a[c_a],b[c_b])>k:
        break
    if a[c_a]>b[c_b]:
        time += b[c_b]
        c_b += 1
    elif a[c_a]<b[c_b]:
        time += a[c_a]
        c_a += 1

    ans += 1
'''
a = [0]+a
b = [0]+b

for i in range(1,n+1):
    a[i]= a[i-1]+a[i]
for i in range(1,m+1):
    b[i]= b[i-1]+b[i]

for i in range(0,n+1):
    for j in range(0,m+1):
        time = a[i] + b[j]
        if time > k:
            break
        kazu = i + j
    ans = max(ans,kazu)

print(ans)


### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
b = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
kazu = 0
c_a = 0
c_b = 0
time = 0

a = [0]+a
b = [0]+b

for i in range(1,n+1):
    a[i]= a[i-1]+a[i]
for i in range(1,m+1):
    b[i]= b[i-1]+b[i]

for i in range(0,n+1):
    for j in range(max(0,kazu-i+1),m+1):
        time = a[i] + b[j]
        if time > k:
            break
        kazu = i + j

print(kazu)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
res = 0
while A:
    if len(A) == 1:
        res += 1
    else:
        if A[0] != A[1]:
            res += 1
    t = A[0]
    NA = []
    for a in A:
        if a % t != 0:
            NA.append(a)
    A = NA[:]
print(res)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
MA = max(A)
dp = [True for _ in range(MA+1)]
flag = [False for _ in range(MA+1)]

for i in range(N):
    a = A[i]
    if not flag[a]:
        flag[a] = True
        t = a*2
        while t <= MA:
            dp[t] = False
            t += a
    elif flag[a] == 1:
        dp[a] = False
res = 0
for a in A:
    if dp[a]:
        res += 1
print(res)
### BUGGY CODE ###

import sys
sy = sys.stdin.readlines()
_,Q = map(int, sy[0].split())
S = sy[1]

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  s = S[l-1:r]
  print(s.count('AC'))


### FIXED CODE ###

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

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
r=0
from collections import deque
q=deque([A[0]])
for i in range(1,N):
    q2=deque()
    for a in q:
        if a&A[i]==0:
            r+=1
            q2.append(a+A[i])
    q2.append(A[i])
    q=q2
print(r+N)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
r=0
from collections import defaultdict
d=defaultdict(int)
d[A[0]]=1
for i in range(1,N):
    d2=defaultdict(int)
    for a in d.keys():
        if a&A[i]==0:
            r+=d[a]
            d2[a+A[i]]+=d[a]
    d2[A[i]]+=1
    d=d2
print(r+N)
### BUGGY CODE ###

import numpy as np

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

maxval = 0
idx = 0
for ii in range(N):
  
  p[ii] = int(p[ii])
  if ii - K >= 0:
    val = np.sum(p[ii-K+1:ii+1])
    if val > maxval:
      maxval = val
      idx = ii

ans = 0
for ii in range(idx-K+1,idx+1):
  an = np.arange(1,p[ii]+1)
  ans += np.sum(an)/p[ii]

#ans = 1*1/6 + 2*1/6 + 3*1/6 + 4*1/6 + 5*1/6 + 6*1/6
#ans = 1/2 + 2/2 + 1/4 + 2/4 + 3/4 + 4/4 + 1/5 + 2/5 + 3/5+ 4/5 + 5/5
print(ans)

### FIXED CODE ###

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

res = []

res.append((sum(range(1,p[0]+1)))/p[0])

for i in range(1,N):
  #res.append(res[i-1] + p[i]*(p[i]+1)/(2*p[i]))
  res.append(res[i-1] + 0.5*(p[i]+1))
  #res.append(res[i-1] + 1 + 0.5*(p[i]-1))

ans=res[K-1]

for i in range(1,N-K+1):
  ans = max(ans,res[i+K-1] - res[i-1])
print(ans)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*n 
for i in range(1,n):
    if i==1:
        dp[i]=abs(a[i]-a[i-1]) 
    else:
        dp[i]=dp[i-1]+abs(a[i]-a[i-1])
        for j in range(2,k+1):
            if j<=i:
                dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]))
            else:
                break
print(dp[n-1])        

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*n 
for i in range(1,n):
    if i==1:
        dp[i]=abs(a[i]-a[i-1]) 
    else:
        dp[i]=dp[i-1]+abs(a[i]-a[i-1])
        for j in range(2,k+1):
            if j<=i:
                dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]))
            else:
                break
print(dp[n-1])
### BUGGY CODE ###

import sys
# from collections import defaultdict
# from collections import Counter
# from queue import Queue
# sys.setrecursionlimit(2000000)

def main():
    N = int(input())
    As = [int(s) for s in input().split()]

    ans = 0
    for i in range(N):
        if ( i + 1 )- As[i] <= 0:
            continue

        for k in range(i):
            if (i + 1) - (k + 1) == As[i] + As[k]:
                ans += 1

    print(ans)

    return 0

if __name__ == '__main__':
    sys.exit(main())


### FIXED CODE ###

import sys
# from collections import defaultdict
from collections import Counter
# from queue import Queue
# sys.setrecursionlimit(2000000)

def main():
    N = int(input())
    As = [int(s) for s in input().split()]

    i_plus_As = [(i+1)+As[i] for i in range(N)]
    counter = Counter(i_plus_As)

    ans = 0
    for i in range(N):
        i_value = ( i + 1 )- As[i]
        if i_value <= 0:
            continue

        ans += counter[i_value]

    print(ans)

    return 0

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

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

max_keta = len(str(bin(B)))-2
ans_str = [0] * max_keta
for x in range(A, B + 1):
    a = format(x, '0%db' % max_keta)
    #print(x, a)
    for i in range(len(a)):
        ans_str[i] += int(a[i])
    #print(ans_str)

j = 1
ans = 0
for aa in reversed(ans_str):
    ans += (int(aa) % 2) * j
    j *= 2
#print(a)
print(ans)

### FIXED CODE ###

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


def f(x):
    if x % 2 == 1:
        return x ^ ((x//2) % 2) ^ (x-1)
    else:
        return x ^ ((x//2) % 2)


ans = f(A-1) ^ f(B)
print(ans)
### BUGGY CODE ###

from collections import defaultdict as dd
n = int(input())
A = list(map(int, input().split()))

dic = dd(lambda: set())
for index, val in enumerate(A):
    if val < 2 * 10**5:
        dic[val].add(index)

counter = 0
for index, val in enumerate(A):
    for val_cand in dic.keys():
         if index + val + val_cand in dic[val_cand]:
             counter += 1
print(counter)

### FIXED CODE ###

from collections import defaultdict as dd
n = int(input())
A = list(map(int, input().split()))

L = dd(set)
R = dd(set)
for i, a in enumerate(A):
    x = i + a
    L[x].add(i)
    x = i - a
    R[x].add(i)

#print(L)
#print(R)

counter = 0
for num in list(set(L.keys()) & set(R.keys())):
    counter += len(L[num]) * len(R[num])

print(counter)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in set(A):
    ans = max(ans, A.count(i)+A.count(i-1)+A.count(i+1))
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = sorted(list(map(int, input().split())))
ans = 1

AA = collections.Counter(A)
cc = [0]*(max(A)+1)

for i in AA.keys():
    cc[i] = AA[i]

for i in range(len(cc)):
    ans =  max(ans, sum(cc[i:i+3]))

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

#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in s :
	t ^= 1 << (ord(i)-ord('a'))
	for j in range(26) :
		d[t] = min(d.get(t,1000000),d.get(t^(1<<j),1000000)+1)
print(d[t] if d[t] else 1)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in (ord(x)-ord('a') for x in s) :
	t ^= 1 << i
	d[t] = min(d[t] if t in d else 1000000, min((d[t^(1<<j)] for j in range(26) if t^(1<<j) in d))+1)
print(d[t] if d[t] else 1)
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
for i in range(1,M+1):
    i = bisect.bisect_right(A,i)
    if i == 0:
        continue
    v = max(B[:i])
    i2 = B.index(v)
    A.pop(i2)
    B.pop(i2)
    ans += v
print(ans)

### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = deque([])
B = deque([])
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.popleft()
            heapq.heappush(q,B.popleft()*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(i) for i in input().split()]
count = collections.Counter(A)
ans = 0
if N%2 == 1:
  for k,v in count.items():
    if k%2 == 1 or (k != 0 and v != 2):
      break
  else:
    ans = 2**(N//2)
else:
  for k,v in count.items():
    if k%2 == 0 or v != 2:
      break
    else:
      ans = 2**(N//2)
print(ans%(10**9+7))

### FIXED CODE ###

import collections
N = int(input())
A = [int(i) for i in input().split()]
count = collections.Counter(A)
ans = 0
if N%2 == 1:
  for k,v in count.items():
    if k%2 == 1 or (k != 0 and v != 2):
      break
  else:
    ans = 2**(N//2)
else:
  for k,v in count.items():
    if k%2 == 0 or v != 2:
      break
    else:
      ans = 2**(N//2)
print(ans%(10**9+7))
### BUGGY CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

index = 1
prev = -1
max_num = -1
flag = True
if B == 1:
    flag = False
    max_num = 0

while flag and index <= N:
    tmp = calc(index)
    if tmp < prev:
        flag = False
    else:
        prev = tmp
    if max_num < tmp:
        max_num = tmp

    index += 1

print(max_num)


### FIXED CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

print(calc(min(B-1, N)))
### BUGGY CODE ###

# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) for i in range(D)]

# depth-first-like search
G_tab = [(i + 1) * x[0] + x[1] for i, x in enumerate(pc)]
cnt_tab = [x[0] for x in pc]
G_stack = [G_tab[0]]
cnt_stack = [cnt_tab[0]]
order = [0]

mincnt = D_MAX * P_MAX
while True:
    ## deepth increament (continue)
    if sum(G_stack) < G:
        # append lowest item (always break?)
        for i in range(D):
            if i not in order: break
        order.append(i)
        G_stack.append(G_tab[i])
        cnt_stack.append(cnt_tab[i])
        continue
    ## escape
    G_tmp = sum(G_stack[:-1])
    cnt_tmp = sum(cnt_stack[:-1])
    if cnt_tmp < mincnt:
        ## evaluate cnt_last
        idx = order[-1]
        x = pc[idx]
        cnt_last = x[0]
        for i in range(x[0]):
            cnt_last -= 1
            G_last = (idx + 1) * cnt_last
            # print("##", cnt_last, G_tmp + G_last, G)
            if G_tmp + G_last < G: break
        cnt_last += 1
        ## update mincnt
        # print("#", order, cnt_tmp, cnt_last, G - G_tmp, "/", mincnt)
        if cnt_tmp + cnt_last < mincnt: mincnt = cnt_tmp + cnt_last
    ## next node
    order_last = order[-1] + 1
    while True:
        if order_last > D - 1:
            G_stack.pop()
            cnt_stack.pop()
            order.pop()
            if len(order) < 1: break # end
            order_last = order[-1] + 1
            continue
        elif order_last in order:
            order_last = order_last + 1
            continue
        else:
            order[-1] = order_last
            G_stack[-1] = G_tab[order_last]
            cnt_stack[-1] = cnt_tab[order_last]
            break
    ## escape
    if len(order) < 1: break # end

print(mincnt)

### FIXED CODE ###

# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) for i in range(D)]

G_list = [(i + 1) * x[0] + x[1] for i, x in enumerate(pc)]
cnt_list = [x[0] for i, x in enumerate(pc)]
idx = [map(int, format(i, "b")) for i in range(2 ** D)]

# i, G_comp, cnt_comp
table = [ (i, sum([((i // (2 ** j)) % 2) * G_list[j] for j in range(D)]), sum([((i // (2 ** j)) % 2) * cnt_list[j] for j in range(D)])) for i in range(2 ** D)] # very long
# print(table)
mincnt = D_MAX * P_MAX
for i, (G_last, cnt_last) in enumerate(zip(G_list, cnt_list)):
    for j, G_comp, cnt_comp in filter(lambda x: (((x[0] // (2 ** i)) % 2 == 0) and (x[1] <= G < x[1] + G_last) and (x[2] < mincnt)), table):
        # print(i, (G_last, cnt_last), j, G_comp, cnt_comp)
        cnt_last_tmp = min((-((G_comp - G) // (i + 1)), cnt_last))
        if cnt_comp + cnt_last_tmp < mincnt: mincnt = cnt_comp + cnt_last_tmp

print(mincnt)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

debug = False

def solve(ds, n, x, m):
    cnt_zero_in_d = 0
    ds_m = []
    for d in ds:
        ds_m.append(d % m)
        if ds_m[-1] == 0:
            cnt_zero_in_d += 1
    ds = [d % m for d in ds]
    a_n = x + sum(ds[0:(n - 1) % len(ds)]) + ((n - 1) // len(ds) * sum(ds)) 
    cnt_same = ds[0:(n - 1) % len(ds)].count(0) + ((n - 1) // len(ds) * cnt_zero_in_d)
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_same


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys

debug = False

def solve(ds, n, x, m):
    ds = [d % m for d in ds]

    nr_loop = (n - 1) // len(ds)
    lastloop_remaining = (n - 1) % len(ds)
    a_n = x
    cnt_zero = 0
    for i in range(0, len(ds)):
        dmod = ds[i] % m
        a_n += (dmod) * nr_loop
        if dmod == 0:
            cnt_zero += nr_loop
        if i < lastloop_remaining:
            a_n += dmod
            if dmod == 0:
                cnt_zero += 1
    cnt_decrease = a_n // m - x // m
    return n - 1 - cnt_decrease - cnt_zero


def read_int_list(sep = " "):
    return [int(s) for s in sys.stdin.readline().split(sep)]


def dprint(*args, **kwargs):
    if debug:
        print(*args, **kwargs)
    return


def main():
    k, q = read_int_list()
    d = read_int_list()
    for _ in range(0, q):
        n, x, m = read_int_list()
        print(str(solve(d, n, x, m)))
    

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

import sys
sys.setrecursionlimit(500000)
N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for i in range(M)])
t = 10**9+7
import sys
sys.setrecursionlimit(500000)
from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return (fibo(n-2) + fibo(n-1)) % t
print(fibo(N) % t)