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

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[200000]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)


### FIXED CODE ###

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)
### BUGGY CODE ###

N = int( input() )
 
I = range( 1, N + 1 )
P = [ i for i in range(2, N + 1) ] + [ 1 ]
 
cnt = 0
for i in range( N ):
  cnt = cnt + I[ i ] % P[ i ]

print( cnt )

### FIXED CODE ###

N = int( input() )
print( N * ( N - 1 ) // 2 )
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=list(map(int, input().split()))
S=Counter(A)
T=set(S)
# print(S)
# print(T)
# 篩？
ct=0
L=list(S.keys())
L.sort()
# print(L)

for i in range(len(L)):
    a=L[i]
    if a not in T:
        continue
    T.remove(a)
    if S.get(a)==1:
        ct+=1
    tmp=T.copy()
    # print(tmp)
    for n in T:
        if n%a==0:
            tmp.difference_update({n,})
    T=tmp
print(ct)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
m = max(A)
sieve = [True]*(m+1)
sieve[0] = False
ct = 0
for i in range(N):
    n = A[i]
    if sieve[n] == False:
        continue
    if i < N-1 and n == A[i+1]:
        sieve[n] = False
    if sieve[n] == True:
        ct += 1
    for k in range(n*2, m+1, n):
        sieve[k] = False
print(ct)
### BUGGY CODE ###

n = int(input())
x = [int(input()) for i in range(n)]
y,answer = set(x),0
for i in y:
	if x.count(i)%2 == 1:
		answer += 1
print(answer)

### FIXED CODE ###

import collections
n = int(input())
x = [int(input()) for i in range(n)]
a = collections.Counter(x)
answer = 0
for i in a.values():
	if i%2==1:
		answer += 1
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#単入力
n=int(input())

l=[i for i in range(1,n+1)]
ll=l
ans=[]
for i in range(len(l)):
    if i==n-1:
        break
    ans.append(ll[i]%l[i+1])
    #if i==0:
        #del ans[0]

print(sum(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline

#単入力
n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import math


def max_index(list):
    r = -1
    max = 0
    for i in range(len(list)):
        v = list[i]
        if v > max:
            max = v
            r = i
    return r


def use_coupon(a):
    index = max_index(a)
    a[index] /= 2


def sum(a):
    s = 0
    for v in a:
        s += math.floor(v)
    return s


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

for i in range(m):
    use_coupon(a)

print(sum(a))


### FIXED CODE ###

import math
from heapq import heappush, heappop


def rint(s):
    return -int(s)


def sum(a):
    s = 0
    for v in a:
        s += math.floor(-v)
    return s


n, m = list(map(int, input().split(" ")))
a = list(map(rint, input().split(" ")))
a.sort()

for i in range(m):
    v = heappop(a)
    heappush(a, v/2)

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

import copy
import numpy as np
s = list(str(input()))
mod = 10**9 + 7
a = []
n = len(s)
for i in range(13):
  r = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  for j in range(10):
    r[(i*10+j)%13] = 1
  a.append(copy.deepcopy(r))
a = np.array(a)
if s[0] == "?":
  start = np.array([1,1,1,1,1,1,1,1,1,1,0,0,0])
else:
  start = np.array([0,0,0,0,0,0,0,0,0,0,0,0,0])
  start[int(s[0])] = 1
for i in range(1,n):
  if s[i] == "?":
    start = np.dot(start,a)
    for j in range(13):
      start[j] = start[j] % mod
  else:
    nxt = [0]*13
    for j in range(13):
      nxt[(j*10+int(s[i]))%13] += int(start[j])
    start = copy.deepcopy(np.array(nxt))
print(start[5])

### FIXED CODE ###

s = str(input())
mod = 10**9 + 7
n = len(s)

if s[0] == "?":
  ans = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  ans = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  ans[int(s[0])] = 1


for i in s[1:]:
  dp = [0]*13
  for j in range(13):
    dp[j*10%13] = ans[j] % mod
  dp += dp
  if i == "?":
    for j in range(13):
      ans[j] = sum(dp[j+4:j+14])
  else:
    for j in range(13):
      ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)
### BUGGY CODE ###

def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    a_sorted = sorted(A)
    a_sorted = a_sorted[:bisect_left(a_sorted, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in list(enumerate(a_sorted))[::-1]:
        if current_max + a >= K:
            ans = idx
        for j in range(current_max + 1):
            if dp[j] and j + a < K:
                current_max = max(current_max, j + a)
                dp[j + a] = True
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

### FIXED CODE ###

def d_NoNeed(N, K, A):
    a = sorted(A)
    s = t = 0
    # aのうち要素が大きいものから見ていったとき、
    # その要素を入れても総和がK未満のものだけ加えていく
    # 最後に連続して加えた要素の個数が解となる
    # (それら以外の要素の組み合わせでK以上にでき、かつ、
    #  それらの総和がK未満になるため)
    for i in range(N - 1, -1, -1):
        if s + a[i] < K:
            s += a[i]
            t += 1
        else:
            t = 0
    return t

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_NoNeed(N, K, A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500*500) # default 1000

class data():
    def __init__(self,N):
        self.to=[[] for j in range(N)] # N points
        self.c=[0]*N # N points

def dfs(v,p=-1): # vertices & parent idx
    lst=data.to[v] # children list
    for child in lst:
        if child==p:
            continue
        data.c[child]+=data.c[v]
        # print('vertices=',v)
        # print('child=',child)
        # print('parent=',p)
        dfs(child,v)
        
N, Q = map(int, input().strip().split())
data=data(N)
for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    data.to[a].append(b)
    data.to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    data.c[p]+=x

dfs(0)
for i in range(N):
    print(data.c[i],end=' ')

### FIXED CODE ###

N, Q = map(int, input().strip().split())

# visited = [False for _ in range(N)]
# def dfs(v): # vertices & parent idx
#     visited[v]=True
#     for child in to[v]:
#         if visited[child]==True:
#             continue
#         ans[child]+=ans[v]
#         dfs(child)
# def dfs(v,p=-1): # vertices & parent idx
#     for child in to[v]:
#         if child==p:
#             continue
#         ans[child]+=ans[v]
#         dfs(child,v)

to=[[] for j in range(N)] # N points
ans=[0]*N # N points

for i in range(N-1):
    a,b=map(int, input().strip().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)

for i in range(Q):
    p,x=map(int, input().strip().split())
    p-=1
    ans[p]+=x

# dfs(0)
stack=[0]
visited=[False]*N
while stack:
    v=stack.pop()
    visited[v]=True
    for child in to[v]:
        if visited[child] ==False:
            # visited[v]=True
            ans[child]+=ans[v]
            stack.append(child)
for i in range(N):
    print(ans[i],end=' ')
# print(ans)
### BUGGY CODE ###

from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
    path = sorted(path, key=lambda x: x[1])
    path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])

### FIXED CODE ###

from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
path = sorted(path, key=lambda x: x[1])
path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])
### BUGGY CODE ###

# YouTube
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def main():
    def dfs(u):
        ok[u] = 1
        for v in to[u]:
            if ok[v]: continue
            dfs(v)

    def rdfs(u):
        ok[u] += 2
        for v in fr[u]:
            if ok[v] > 1: continue
            rdfs(v)

    inf = 10 ** 9
    to = defaultdict(list)
    fr = defaultdict(list)
    abc = []
    n, m, p = map(int, input().split())
    ok = [0] * n
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        c = -(c - p)
        to[a].append(b)
        fr[b].append(a)
        abc.append([a, b, c])
    dfs(0)
    rdfs(n - 1)
    score = [inf] * n
    score[0] = 0
    for i in range(n):
        stop = True
        for a, b, c in abc:
            if ok[a] < 3 or ok[b] < 3: continue
            tmp = score[a] + c
            if tmp < score[b]:
                score[b] = tmp
                stop = False
        if stop:
            print(max(0, -score[n - 1]))
            break
    else:
        print(-1)

main()


### FIXED CODE ###

# YouTube
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)

def dfs(u):
    ok[u] = 1
    for v in to[u]:
        if ok[v]: continue
        dfs(v)

def rdfs(u):
    ok[u] += 2
    for v in fr[u]:
        if ok[v] > 1: continue
        rdfs(v)

inf = 10 ** 9
to = defaultdict(list)
fr = defaultdict(list)
abc = []
n, m, p = map(int, input().split())
ok = [0] * n
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    c = -(c - p)
    to[a].append(b)
    fr[b].append(a)
    abc.append([a, b, c])
dfs(0)
rdfs(n - 1)
score = [inf] * n
score[0] = 0
for i in range(n):
    stop = True
    for a, b, c in abc:
        if ok[a] < 3 or ok[b] < 3: continue
        tmp = score[a] + c
        if tmp < score[b]:
            score[b] = tmp
            stop = False
    if stop:
        print(max(0, -score[n - 1]))
        break
else:
    print(-1)
### BUGGY CODE ###

S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  if c == "?":
    for d in range(10):
      n = (d*(10**((len(S)-i-1)%12)))%13
      for j in range(13):
        dp[i+1][j] = (dp[i+1][j]+dp[i][(j+13-n)%13])%1000000007
  else:
    d = int(c)
    n = (d*(10**((len(S)-i-1)%12)))%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  #print(dp[i+1])
print(dp[len(S)][5])


### FIXED CODE ###

S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])
### BUGGY CODE ###

n = int(input())

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


total = 0
for i in range(n-1):
    for j in a[i+1:]:
        total += (a[i]%(10**9+7))*(j%(10**9+7))
        total = total%(10**9+7)

print(total)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 
 
print(ans % mod)
### BUGGY CODE ###

N = int(input())
X = str(input())
X10 = int(X,2)

one_num = X.count("1")

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        if one_num==1:
            print(0)
            continue
        plus = -pow(2,N-i-1)
        ones = one_num-1
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = bin(Xnow)
            ones = Xnow2.count("1")
            Xnow = Xnow%ones
            count+=1
        print(count)


### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

s=list(str(input()))
b=0
while len(s)>=5:
  if s[-1]=='r' and len(s)==6:
    if ''.join(s)=='eraser':
      print('YES')
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='r':
    sd=[s[-7],s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    se=[s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dreamer':
      del s[-7:]
    elif ''.join(se)=='eraser':
      del s[-6:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='m':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dream':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='e':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='erase':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break  
  else:
    print('NO')
    b+=1
    break
if len(s)==0:
  print('YES')
elif b!=1:
  print('NO')

### FIXED CODE ###

s=list(str(input()))
b=0
while len(s)>=7:
  if s[-1]=='r':
    sd=[s[-7],s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    se=[s[-6],s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dreamer':
      del s[-7:]
    elif ''.join(se)=='eraser':
      del s[-6:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='m':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='dream':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break
  elif s[-1]=='e':
    sd=[s[-5],s[-4],s[-3],s[-2],s[-1]]
    if ''.join(sd)=='erase':
      del s[-5:]
    else:
      print('NO')
      b+=1
      break  
  else:
    print('NO')
    b+=1
    break
if len(s)==0 or (len(s)==6 and ''.join(s)=='eraser') or (len(s)==5 and ''.join(s)=='dream') or (len(s)==5 and ''.join(s)=='erase'):
  print('YES') 
elif b!=1:
  print('NO')
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
def main():
	num = int(input())
	sum = 0
	for i in range(num):
		a = i+1
		for j in range(num):
			b = j+1
			for k in range(num):
				c = k+1
				sum += gcd(a,b,c)
	print (sum)

if __name__ == '__main__':
	main()


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import math

    
def main():
	num = int(input())
	sum = 0
	for i in range(num):
		a = i+1
		for j in range(num):
			b = j+1
			for k in range(num):
				c = k+1
				sum += math.gcd(math.gcd(a,b),c)
	print (sum)

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

n=int(input())
s=str(input())
t=len(s)
r=[]
g=[]
b=[]
a=0
for i in range(n):
    if s[i]=='R':
        r.append(i)
    if s[i]=='G':
        g.append(i)
    if s[i]=='B':
        b.append(i)
d=len(r)*len(g)*len(b)
for ri in r:
    for gi in g:
        rg=gi-ri
        if rg+gi in b:
            d-=1
        if  ri-rg in b:
            d-=1
        if (gi+ri)/2 in b:
            d-=1

print(d)

### FIXED CODE ###

n=int(input())
s=str(input())
t=len(s)
r=set()
g=set()
b=set()
a=0
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
d=len(r)*len(g)*len(b)
for ri in r:
    for gi in g:
        rg=gi-ri
        if rg+gi in b:
            d-=1
        if  ri-rg in b:
            d-=1
        if (gi+ri)/2 in b:
            d-=1

print(d)
### BUGGY CODE ###



def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr


n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    cc = {}
    for num in anum:
        tmp = factorization(num)
        for k,v in tmp.items():
            if k in cc:
                cc[k] = max(cc[k], v)
            else:
                cc[k] = v
    num = 1
    for k,v in cc.items():
        num *= (k**v)
    num0 = num * (2**(acount[0]-1))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)

### FIXED CODE ###


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def lcm(a, b):
    return a//gcd(a, b)*b

def lcms(a):
    l = a[0]
    for num in a[1:]:
        l = lcm(l, num)
    return l

n, m = map(int, input().split())
a = list(map(int, input().split()))
# a2 = [num//2 for num in a]
acount = [None]*n # aを2で割れる回数
anum = [None]*n # 割ったあとの残り(=奇数)
for i,num in enumerate(a):
    c = 0
    while num%2==0 and num>1:
        num //=2
        c += 1
    acount[i] = c
    anum[i] = num
if all(item==acount[0] for item in acount):
    l = lcms(anum)
    num0 = l * (pow(2, (acount[0]-1)))
    span = num0*2
    if m<num0:
        print(0)
    else:
        print(int((m-num0)//span + 1))
else:
    print(0)
### BUGGY CODE ###

INF = float('infinity')

N, K = map(int, input().split())
H = [int(c) for c in input().split()]

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))

print(dp[N-1])

### FIXED CODE ###

INF = float('infinity')

N, K = map(int, input().split())
H = [int(c) for c in input().split()]

dp = [INF] * N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))

print(dp[N-1])
### BUGGY CODE ###

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

num = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[i] < b[j] < c[k]:
                num += 1
print(num)

### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
#print(a,b,c)
cnt = 0
for i in range(n):
    d = bisect.bisect_left(a,b[i])
    e = bisect.bisect_right(c,b[i])
    cnt += d*(n-e)
print(cnt)