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

import heapq
def f(X):
    return X[-1]-X[0]

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
import itertools
res = 0
for x in itertools.combinations(A, K):
    res = (res + f(x))%(10**9+7)
print(res)


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
res = 0
MOD = 10**9+7
nCk_2 = dict()
fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n, k):
    return (fac[n]*((finv[k]*finv[n-k])%MOD))%MOD
s = [1,-1]
for m in range(2):
    for i in range(K-1,N):
        res = (res + s[m]*int((A[i])*comb(i,K-1)))%MOD
    A = sorted(A, reverse=True)
print(res)
### BUGGY CODE ###

s = input()

dp = [[0]*2019 for i in range(len(s))]

mod = 2019

for l in range(0, len(s)-1):
    dp[l][int(s[l])] += 1
    for m in range(0, mod):
        if dp[l][m] != 0:
            num = int(s[l+1])
            dp[l+1][(10*m+num)%mod] += dp[l][m]
            
cnt = 0
for l in range(0, len(s)):
    if dp[l][0] != 0:
        cnt += dp[l][0]
        
print(cnt)

### FIXED CODE ###

s = input()
mod = 2019
array = [0]*(len(s)+1)

for i in range(len(s)):
    array[i+1] = (array[i] + pow(10,i,mod)*int(s[len(s)-(i+1)])) % mod
    

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))
### BUGGY CODE ###

from collections import Counter
n, p = map(int, input().split())
s = list(map(int, list(input())))
si = [s[-1]]

if 10%p==0:
    r = 0
    for i in range(1,n+1):
        if s[-i]%p==0:
            r += n-i+1
    print(r)
else:
    for i in range(2, n+1):
        si.append(si[-1]+s[-i]*(10**(i-1)))
    si = [i%p for i in si]
    si_counter = Counter(si).items()
    r = 0
    for num, count in si_counter:
        if count >= 2:
            r += (count*(count-1))//2
        if num == 0:
            r += count
    print(r)

### FIXED CODE ###

n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

if 10%p==0:
    result = 0
    for i in range(n):
        if s[i]%p==0:
            result += n-i
else:
    r = [0 for _ in range(p)]
    r[0] = 1
    t = 0
    ten = 1
    for i in s:
        t = (t+i*ten)%p
        ten = (ten*10)%p
        r[t] += 1
    result = 0
    for i in r:
        result += i*(i-1)//2
print(result)
### BUGGY CODE ###

from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = sorted(list(map(int,input().split())))
A = [0 for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
que = deque([1])
hist[1] = 1
cur = 0
while que:
    i = que.popleft()
    if len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
    flag = 2
    for j in G[i]:
        if hist[j]==0:
            que.append(j)
            hist[j] = 1
            flag = 1
        elif hist[j]==1:
          flag = 1
    if flag==2 and hist[i]==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
    elif hist[i]==1:
        que.append(i)
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(A[i],A[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*A[1:])

### FIXED CODE ###

from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = sorted(list(map(int,input().split())))
A = [0 for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
que = deque([1])
hist[1] = 1
cur = 0
while que:
    i = que[-1]
    if len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
    flag = 2
    for j in G[i]:
        if hist[j]==0:
            que.append(j)
            hist[j] = 1
            flag = 1
    if flag==2 and hist[i]==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(A[i],A[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*A[1:])
### BUGGY CODE ###

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

A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float("inf") for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for i in range(N):
        dp[h] = min(dp[h], dp[max(0, h - A[i])] + B[i])

print(dp[H])


### FIXED CODE ###

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

A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float("inf") for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for i in range(N):
        dp[h] = min(dp[h], dp[max(0, h - A[i])] + B[i])

print(dp[H])
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
#print(dp)
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)
        
        




### FIXED CODE ###

import collections
N = int(input())
A = list(map(float,input().split()))
K = N//2  + 1
dp = [[0 for _ in range(N + 1) ] for _ in range(N + 1)]
if N == 0: 
    print(0)
    exit
dp[0][0] = 1
ans = 0
for i in range(1,N+1):
    for j in range(i+1):
        if j - 1 < 0:
            dp[i][j] = dp[i-1][j]*(1-A[i-1])
        else:
            dp[i][j] = dp[i-1][j-1]*A[i-1] + dp[i-1][j]*(1-A[i-1])
for i in range(K,len(dp[N])):
        ans+=dp[N][i]
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
lcm = dict()
mod = 10**9+7
for a in A:
    n = 2
    while a != 1:
        c = 0
        while a % n == 0:
            a //= n
            c += 1
        if not n in lcm:
            lcm[n] = 0
        lcm[n] = max(lcm[n], c)
        n += 1
l = 1
for n in lcm.keys():
    l *= pow(n, lcm[n], mod)
    n %= mod
ans = 0
for a in A:
    p = pow(a, mod-2, mod)
    ans += (l*p)
    ans %= mod
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
pn = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
      449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
lcm = dict()
mod = 10**9+7
for a in A:
    i = 0
    while a != 1 and i < len(pn):
        c = 0
        n = pn[i]
        while a % n == 0:
            a //= n
            c += 1
        if not n in lcm:
            lcm[n] = 0
        lcm[n] = max(lcm[n], c)
        i += 1
    if a != 1:
        if not a in lcm:
            lcm[a] = 1
l = 1
for n in lcm.keys():
    l *= pow(n, lcm[n], mod)
    l %= mod
ans = 0
for a in A:
    p = pow(a, mod-2, mod)
    ans += (l*p)
    ans %= mod
print(ans)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[input() for _ in range(H)]

L,R=[[0]*W for _ in range(H)], [[0]*W for _ in range(H)]
D,U=[[0]*W for _ in range(H)], [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j==0:
      L[i][j]=1
      R[i][-(j+1)]=1
    else:
      L[i][j]=L[i][j-1]+1
      R[i][-(j+1)]=R[i][-j]+1
    if i==0:
      D[i][j]=1
      U[-(i+1)][j]=1
    else:
      D[i][j]=D[i-1][j]+1
      U[-(i+1)][j]=U[-i][j]+1
    if S[i][j]=="#":
      L[i][j],D[i][j]=0,0
    if S[i][-(j+1)]=="#":
      R[i][-(j+1)]=0
    if S[-(i+1)][j]=="#":
      U[-(i+1)][j]=0

ans=0
for i in range(H):
  for j in range(W):
    val=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    ans=max(ans,val)
print(ans)

### FIXED CODE ###

import numpy as np

H,W=map(int,input().split())
S=np.array([list(input()) for _ in range(H)]) == "."

ups=np.zeros((H,W),dtype=int)
downs=np.zeros((H,W),dtype=int)
rights=np.zeros((H,W),dtype=int)
lefts=np.zeros((H,W),dtype=int)

for i in range(1,H):
    ups[i,:]=(ups[i-1,:]+1)*S[i-1,:]

for i in range(H-2,-1,-1):
    downs[i,:]=(downs[i+1,:]+1)*S[i+1,:]

for i in range(1,W):
    rights[:,i]=(rights[:,i-1]+1)*S[:,i-1]

for i in range(W-2,-1,-1):
    lefts[:,i]=(lefts[:,i+1]+1)*S[:,i+1]

ans=((ups+downs+lefts+rights)*S).max()+1
print(ans)
### BUGGY CODE ###

import numpy as np

N, Q = map(int,input().split())
S = str(input())
#A = [list(map(int,input().split())) for i in range(Q)]

L_cnt = np.zeros(N-1)
L_cnt[0] = 0
L_str = S[0]
R_cnt = np.zeros(N-1)
R_cnt[0] = 0
R_str = S[N-1]

for i in range(N-2):
  L_str = L_str + S[i+1]
  L_cnt[i+1] = L_cnt[i] + (L_str[-2:] == 'AC')
  R_str = S[N-2-i] + R_str
  R_cnt[i+1] = R_cnt[i] + (R_str[:2] == 'AC')
  #print(i, L_str)
  #print(i, R_str)

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
for i in range(Q):
  #ans = n_whole - (L_cnt[A[i][0]-1] + R_cnt[N-A[i][1]])
  A = list(map(int,input().split()))
  ans = n_whole - (L_cnt[A[0]-1] + R_cnt[N-A[1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""



### FIXED CODE ###

import numpy as np

N, Q = map(int,input().split())
S = str(input())
A = [list(map(int,input().split())) for i in range(Q)]

"""
import random
base_list = ['A', 'T', 'C', 'G']
S = ''
N = int(1e5)
Q = 1
A = [[100, 900]]
for i in range(N):
  S += random.choice(base_list)
"""

L_cnt = np.zeros(N-1)
R_cnt = np.zeros(N-1)

for i in range(N-2):
  L_cnt[i+1] = (S[i:i+2] == 'AC')
  R_cnt[i+1] = (S[N-2-i:N-i] == 'AC')

#print(L_cnt)
#print(R_cnt)
  
n_whole = S.count('AC')
L_cumsum = np.array(L_cnt).cumsum()
R_cumsum = np.array(R_cnt).cumsum()
for i in range(Q):
  ans = n_whole - (L_cumsum[A[i][0]-1] + R_cumsum[N-A[i][1]])
  print(int(ans))
  




"""
## 題意を愚直に表したもの（~10^10の計算量）
for i in range(Q):
  word = S[A[i][0]-1:A[i][1]]
  word_remove = word.replace('T', '').replace('G', '')
  ans = word_remove.count('AC')
  print(ans)
"""
### BUGGY CODE ###


n,q = map(int,input().split())
s = input()

lr = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
  teststring = s[lr[i][0]-1:lr[i][1]]
  print(teststring.count("AC"))


### FIXED CODE ###


n,q = map(int,input().split())
s = input()

lr = [list(map(int,input().split())) for i in range(q)]
t = [0] * (n+1)
for i in range(n):
  
  t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)
for i in range(q):
  l = lr[i][0]
  r = lr[i][1]
  print((t[r-1]-t[l-1]))
### BUGGY CODE ###

H,W=map(int,input().split())

board=[list(input()) for _ in range(H)]
stack=list()
dh=[1,0,-1,0]
dw=[0,-1,0,1]

for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            stack.append([i,j])

def boardcheck():
    nstack=list()
    global stack
    for dot in stack:
        for i in range(4):
            th=dot[0]+dh[i]
            tw=dot[1]+dw[i]
            if 0<=th<H and 0<=tw<W and board[th][tw]=='.':
                board[th][tw]='#'
                nstack.append([th,tw])
    stack=nstack[:]

count=0
while True:
    boardcheck()
    if len(stack)==0:
        break
    count+=1

print(count)


### FIXED CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    A=[[] for _ in range(H)]
    B=[[] for _ in range(H)]
    C=[[0]*W for _ in range(H)]
    for i in range(H):
        A[i]=list(map(int,input().split()))
    for i in range(H):
        B[i]=list(map(int,input().split()))
    for i in range(H):
        for j in range(W):
            C[i][j]=abs(A[i][j]-B[i][j])
    dp=[[[False]*((H+W)*80*2+1) for _ in range(W)] for _ in range(H)]
    dp[0][0][C[0][0]]=True
    dp[0][0][-C[0][0]]=True
    for i in range(1,H):
        for k in range((H+W)*80*2+1):
            if dp[i-1][0][k]==True:
                dp[i][0][(k+C[i][0])%((H+W)*80*2+1)]=True
                dp[i][0][k-C[i][0]]=True
    for j in range(1,W):
        for k in range((H+W)*80*2+1):
            if dp[0][j-1][k]==True:
                dp[0][j][(k+C[0][j])%((H+W)*80*2+1)]=True
                dp[0][j][k-C[0][j]]=True
    
    for i in range(1,H):
        for j in range(1,W):
            for k in range((H+W)*80*2+1):
                if dp[i-1][j][k]==True:
                    dp[i][j][(k+C[i][j])%((H+W)*80*2+1)]=True
                    dp[i][j][k-C[i][j]]=True
                if dp[i][j-1][k]==True:
                    dp[i][j][(k+C[i][j])%((H+W)*80*2+1)]=True
                    dp[i][j][k-C[i][j]]=True
    for i in range((H+W)*80+1):
        if dp[H-1][W-1][i]==True:
            print(i)
            exit()
    pass
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    A = [[] for _ in range(H)]
    B = [[] for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    minusdigit = 80 * 80 * 2
    for i in range(H):
        A[i] = list(map(int, input().split()))
    for i in range(H):
        B[i] = list(map(int, input().split()))
    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j] - B[i][j])
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = ((1 << minusdigit) << C[0][0]) | ((1 << minusdigit) >> C[0][0])
    for i in range(1, H):
        dp[i][0] = (dp[i - 1][0] << C[i][0]) | (dp[i - 1][0] >> C[i][0])
    for j in range(1, W):
        dp[0][j] = (dp[0][j - 1] << C[0][j]) | (dp[0][j - 1] >> C[0][j])

    for i in range(1, H):
        for j in range(1, W):
            dp[i][j] = (dp[i - 1][j] << C[i][j]) | (dp[i - 1][j] >> C[i][j]) | (dp[i][j - 1] << C[i][j]) | (dp[i][j - 1] >> C[i][j])
    ans = dp[H - 1][W - 1]
    for i in range(len(bin(ans)) - (2 + minusdigit)):
        if (ans >> (i + minusdigit)) & 0b1 == 1 or (-i + minusdigit >= 0 and (ans >> (-i + minusdigit)) & 0b1 == 1):
            print(i)
            exit()


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

s = input().split()
a = int(s[0])
b = int(s[1])
k = int(s[2])

arrays = []

for i in range(a, b + 1):
    arrays.append(i)

answer = []

if k > len(arrays):
    k = len(arrays)

for i in range(k):
    answer.append(arrays[i])

for i in range(k):
    x = arrays.pop()
    check = False
    for i in range(len(answer)):
        if answer[i] == x:
            check = True
    if not check:
        answer.append(x)

answer.sort()

for i in range(len(answer)):
    print(answer[i])




### FIXED CODE ###

s = input().split()
a = int(s[0])
b = int(s[1])
k = int(s[2])




for i in range(a, min(b, a + k - 1) + 1):
    print(i)
for i in range(max(b - k + 1, a + k), b + 1):
    print(i)
### BUGGY CODE ###

from functools import lru_cache
n, a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
t = 0
@lru_cache(maxsize=1024)
def dfs(i,ave):
    if i ==n:
        if ave == 0:
            return 1
        else:
            return 0

    return dfs(i+1,ave)+dfs(i+1,ave+x[i]-a)



print(dfs(0,0)-1)


### FIXED CODE ###

n,a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
y = [i - a for i in x]
X = max(a,max(x))

dp = []
for i in range(n+1):
    dp.append([0]*(2*n*X+1))
for j in range(n,-1,-1):
    for t in range(2*n*X+1):
        if j == n and t ==n*X:
            dp[j][t] = 1
        elif j == n:
            dp[j][t] = 0
        elif 0 <= t-y[j] <= 2*n*X:
            dp[j][t] = dp[j+1][t] + dp[j+1][t-y[j]]
        else:
            dp[j][t] = dp[j+1][t]
def main():
    print(dp[0][n*X]-1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
import copy
sys.setrecursionlimit(10**9)
H,W = map(int,input().split())
A = []
B_place = []
for i in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=="#":
      B_place.append([i,w])
  A.append(a)

all_map = [[10**10 for i in range(W)] for i in range(H)]
def f(h,w,cou):
  global H,W,all_map,C
  if h<0 or H<=h or w<0 or W<=w:
    return
  if [h,w] in C:
    return
  if cou>=all_map[h][w]:
    return
  else:
    all_map[h][w]=cou
  f(h-1,w,cou+1)
  f(h+1,w,cou+1)
  f(h,w-1,cou+1)
  f(h,w+1,cou+1)

for B in B_place:
  C = copy.copy(B_place)
  del C[C.index(B)]
  f(B[0],B[1],0)
ans = 0
for i in range(H):
  ans = max(ans,max(all_map[i]))

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

print(sum([int(i) for i in range(int(input()))]))

### FIXED CODE ###

N = int(input())

ans = ((2 + N - 1) * N // 2) - N
print(ans)
### BUGGY CODE ###

from collections import deque

n,m=map(int,input().split())
l=list(map(int,input().split()))
l=[i/2 for i in l]
  
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

s=set(l)
l=set(l)

if len(l)==1:
  lcm=l.pop()
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))
  exit()
a1=l.pop()
a2=l.pop()
g=gcd(a1,a2)
lcm=g*(a1/g)*(a2/g)
d=1

while l:
  a=l.pop()
  d=gcd(lcm,a)
  lcm=d*(a/d)*(lcm/d)
  
if lcm>m:
  print(0)
  exit()
  
for a in s:
  if (lcm/a)%2==0:
    print(0)
    break
else:
  if (m//lcm)%2==0:
    print(int((m//lcm)/2))
  else:
    print(int((m//lcm+1)/2))


### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

def lcm(a,b):
    g=math.gcd(a,b)
    return b*(a//g)
l=a[0]//2
for i in range(n):
    r=a[i]//2
    l=lcm(l,r)
for i in range(n):
    if (l//(a[i]//2))%2==0:
        print(0)
        exit()
res=m//l
print((res+1)//2)
### BUGGY CODE ###

H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * 2 for i in range(M)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[i] = [hi-1, wi-1]

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]

ans = Hdstmax + Wdstmax - 1
for i in Hbomb:
    for j in Wbomb:
        if [i, j] not in DST:
            ans = Hdstmax + Wdstmax
            break
    if ans == Hdstmax + Wdstmax:
        break

print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
Hdst = [0]*H
Wdst = [0]*W
DST = [[0] * M for i in range(2)]
for i in range(M):
    hi, wi = map(int, input().split())
    Hdst[hi-1] += 1
    Wdst[wi-1] += 1
    DST[0][i] = hi-1
    DST[1][i] = wi-1

Hdstmax = max(Hdst)
Wdstmax = max(Wdst)
Hbomb = [i for i, x in enumerate(Hdst) if x == Hdstmax]
Wbomb = [i for i, x in enumerate(Wdst) if x == Wdstmax]

Hchk = [False]*H
Wchk = [False]*W
for i in Hbomb:
    Hchk[i] = True
for i in Wbomb:
    Wchk[i] = True

tmp = 0
for i in range(M):
    if Hchk[DST[0][i]] and Wchk[DST[1][i]]:
        tmp += 1

if len(Hbomb)*len(Wbomb) == tmp:
    print(Hdstmax + Wdstmax - 1)
else:
    print(Hdstmax + Wdstmax)
### BUGGY CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import nlargest
from heapq import nsmallest
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
A = list( map(int, input().split()) )

p("A ",A)

if N==1:
	print( int(A[0]/(2**M)) )
	exit(0)

H=[]
for a in A:
	heappush(H,a*(-1))

p("H ",H)

while M>0:
	h = heappop(H)
	if int(h)==1: break

	h/=2
	M-=1
	
	heappush(H,h)
	
	p("h,H ",h,H)

ans=0
for h in H:
	ans += int(h*(-1))

print(ans)


### FIXED CODE ###

#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import nlargest
from heapq import nsmallest
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
#A = list( map(int, input().split()) )
H = list( -int(i) for i in input().split() )

#p("A ",A)
p("H ",H)

heapify(H)

p("H ",H)

for _ in range(M):
	h = heappop(H)//(-2)
	heappush(H,-h)
	
	#p("h,H ",h,H)


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

import sys,math,collections,itertools
input = sys.stdin.readline

H,W,D=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR=[list(map(int,input().split())) for i in range(Q)]


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

dict_dir = {}

for i in range(Q):
    L = LR[i][0]
    R = LR[i][1]
    useMP = 0
    if (L,R) not in dict_dir:
        point = range(L,R+1,D)
        for p in range(1,len(point)):
            x0,y0 = dict_map[point[p-1]]
            x1,y1 = dict_map[point[p]]
            useMP += abs(x0-x1)+abs(y0-y1)
        dict_dir[(L,R)]=useMP
    else:
        useMP = dict_dir[(L,R)]
    print(useMP)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W,D=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR=[list(map(int,input().split())) for i in range(Q)]


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

memo = [-1]*(H*W+1)
for i in range(1,D+1):
    useMP = 0
    direct = range(i,H*W+1,D)
    memo[i]=0
    for p in range(len(direct)-1):
        x0,y0 = dict_map[direct[p]]
        x1,y1 = dict_map[direct[p+1]]
        dist = abs(x0-x1)+abs(y0-y1)
        useMP += dist
        memo[direct[p+1]]=useMP

for q in range(Q):
    L,R=LR[q]
    print(memo[R]-memo[L])