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

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

MOD = 10 ** 9 + 7


def prime_counter(n):
    ret = []
    for i in range(2, int(n / 2) + 2):
        count = 0
        while n % i == 0:
            n /= i
            count += 1
        if 0 < count:
            ret.append(count)
        if n == 1:
            break
    if 1 < n:
        ret.append(1)
    return ret


def comb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    elif r == 1:
        return n
    return (n % MOD) * pow(r, MOD - 2, MOD) * comb(n - 1, r - 1) % MOD


factnum = prime_counter(M)
ans = 1

for p in factnum:
    ans *= comb(p + N - 1, p)

ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10 ** 9 + 7

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

f = []
p = 2
while p * p <= M:
    if M % p != 0:
        p += 1
        continue
    c = 0
    while M % p == 0:
        c += 1
        M //= p
    f.append(c)
    p += 1
if M != 1:
    f.append(1)

ans = 1
for i in f:
    c = 1
    for j in range(i):
        c = c * (N + j) // (j + 1)
    ans = ans * c % MOD
print(ans)
### BUGGY CODE ###

import collections
n,m = map(int,input().split())
card = [list(map(int,input().split())) for c in range(m)]
nums = []
for index,c in enumerate(card):
  nums += [i for i in range(c[0],c[1]+1)]
ans = 0
for k,v in collections.Counter(nums).items():
  if v == m:
    ans += 1
print(ans)



### FIXED CODE ###

N,M = map(int,input().split())
L = []
R = []
 
for m in range(M):
  l,r = map(int,input().split())
  L+=[l]
  R+=[r]
 
print(max(0,min(R)-max(L)+1))
### BUGGY CODE ###

N, Q = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

w = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    w[p] += x
    
ans = [0] * (N + 1)

visited = defaultdict(bool)
stack = []
visited[1] = True
stack.append(1)
while len(stack) != 0:
    v = stack.pop()
    W = w[v]
    ans[v] += W
    for c in g[v]:
        if not visited[c]:
            visited[c] = True
            stack.append(c)
            ans[c] += ans[v]

print(*ans[1:])


### FIXED CODE ###

N, Q = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

w = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    w[p] += x
    
ans = [0] * (N + 1)

visited = defaultdict(bool)
stack = []
visited[1] = True
stack.append(1)
while len(stack) != 0:
    v = stack.pop()
    W = w[v]
    ans[v] += W
    for c in g[v]:
        if not visited[c]:
            visited[c] = True
            stack.append(c)
            ans[c] += ans[v]

print(*ans[1:])
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
kami = []

for i in a :
    if i in kami :
        kami.remove(i)
    else :
        kami.append(i)
    kami.sort()

print(len(kami))


### FIXED CODE ###

n = int(input())
kami = set()

for i in range(n) :
    a = int(input())
    if a in kami :
        kami.remove(a)
    else :
        kami.add(a)

print(len(kami))
### BUGGY CODE ###

n,m = map(int,input().split())
ans = 1
for i in range(1,m):
	if m%i == 0 and m/i >= n:
		ans = i
	if m/i < n:
		break 
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
k = m//n
ans = 1
i = 1
while i**2 <= m:
	if m%i==0:
		j = m//i
		if j <= k:
			print(j);exit()
		if i <= k:
			ans = max(ans,i)
	i += 1
print(ans)
### BUGGY CODE ###

# encoding][utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]
# print(tv_times)

channells = {}
for i in range(N):
    if tv_times[i][2] in channells.keys():
        channells[tv_times[i][2]] += [tv_times[i][0],tv_times[i][1]]
    else:
        channells[tv_times[i][2]] = [tv_times[i][0],tv_times[i][1]]

tv_times = []
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for j in range(len(remove_list)):
        time.remove(remove_list[j])
        time.remove(remove_list[j])

    for i in range(len(time)//2):
        tv_times.append([time[2*i],time[2*i+1]])


# print(channells)


max_end = -1
# print(tv_times)
for i in range(len(tv_times)):
    max_end = max(tv_times[i][1],max_end)

# print(tv_times)
# print(max_end)
count = [0 for i in range(max_end)]
for ni in range(len(tv_times)):
    for time in range(max(tv_times[ni][0]-1,0),tv_times[ni][1]):
        count[time] += 1

# print(count)
print(max(count))


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

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

import itertools
N,M=map(int,input().split())
A,B=[0]*M,[0]*M
for i in range(M):
    A[i],B[i]=map(int,input().split())

res=0
for p in itertools.permutations(range(M),N-1):
    path=[]
    if A[p[0]]==1:
        path.append(A[p[0]])
    else:
        continue
    path.append(B[p[0]])
    for i in range(len(p)-1):
        if A[p[i+1]]==path[-1]:
            path.append(B[p[i+1]])
        elif B[p[i+1]]==path[-1]:
            path.append(A[p[i+1]])
        else:
            break
    else:
        path.sort()
        if path==list(range(1,N+1)):
            res+=1
print(res)

### FIXED CODE ###

import itertools
N,M=map(int,input().split())
edges=[]
for i in range(M):
    edges.append(list(map(int,input().split())))

res=0
for i in itertools.permutations(range(2,N+1),N-1):
    path=[1]+list(i)
    check=[sorted(path[i:i+2]) in edges for i in range(len(path)-1)]
    if not False in check:
        res+=1
print(res)
### BUGGY CODE ###

def primes(n):
    primes = [2]
    if n < 2:
        return []
    
    for i in range(3, n + 1, 2):
        isPrime = True
        for prime in primes:
            if i % prime == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)
    
    return primes

n = int(input())
l = [int(input()) for _ in range(n)]

print(len([x for x in l if x in primes(max(l))]))


### FIXED CODE ###

def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    for i in range(3, int(x ** 0.5) + 1, 2):
        if x % i == 0:
            return False

    return True

n = int(input())
cnt = 0
for _ in range(n):
    i = int(input())
    cnt += isPrime(i)

print(cnt)
### BUGGY CODE ###

L, R = map(int, input().split())

M = []
for i in range(L, R+1):
  for j in range(i+1, R+1):
    M.append(i * j % 2019)
if len(M) == 0:
  print(L)
else:
  print (min(M))

### FIXED CODE ###

L, R = map(int, input().split())
if R-L >= 2019:
  print (0)
else:
  print (min([((i % 2019) * (j % 2019)) % 2019 for i in range(L,R) for j in range(i+1,R+1)]))
### BUGGY CODE ###

def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j:
            if n in used or n in l1:
                return False
            elif n not in tree[nest-1] and n not in ret:
                ret.append(n)
    return ret


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)

### FIXED CODE ###

def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j:
            if n in used or n in l1:
                return False
            elif n not in tree[nest-1] and n not in ret:
                ret.append(n)
    return ret


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)
### BUGGY CODE ###

import sys

from functools import lru_cache

sys.setrecursionlimit(10 ** 5)

MOD = 998244353


def solve(A, B, C, D):
    @lru_cache(maxsize=None)
    def numWays(rows, cols):
        if rows == A and cols == B:
            return 1

        assert rows >= A and cols >= B
        ways = 0
        if rows > A:
            ways += cols * numWays(rows - 1, cols) % MOD
        if cols > B:
            ways += rows * numWays(rows, cols - 1) % MOD

        if rows > A and cols > B:
            ways -= (cols - 1) * (rows - 1) * numWays(rows - 1, cols - 1) % MOD
        return ways % MOD

    return numWays(C, D) % MOD


A, B, C, D = [int(x) for x in input().split()]
print(solve(A, B, C, D))


### FIXED CODE ###

MOD = 998244353


def solve(A, B, C, D):
    numWays = [[None for c in range(D + 1)] for r in range(C + 1)]

    numWays[A][B] = 1

    for rows in range(A, C + 1):
        for cols in range(B, D + 1):
            if rows == A and cols == B:
                continue
            ways = 0
            if rows > A:
                ways += cols * numWays[rows - 1][cols] % MOD
            if cols > B:
                ways += rows * numWays[rows][cols - 1] % MOD
            if rows > A and cols > B:
                ways -= (cols - 1) * (rows - 1) * numWays[rows - 1][cols - 1] % MOD
            numWays[rows][cols] = ways % MOD

    return numWays[C][D] % MOD


A, B, C, D = [int(x) for x in input().split()]
print(solve(A, B, C, D))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def gcd(x, y):
  while y:
    x, y = y, x % y
  return x

def lcm(x, y):
  return x * y // gcd(x, y)

l = 1
for a in A:
  l = lcm(l, a)
  
answer = 0
for a in A:
  answer = (answer + l * pow(a, MOD - 2, MOD)) % MOD
  
print(answer)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def gcd(x, y):
  return x if y == 0 else gcd(y, x % y)

def lcm(x, y):
  return x * y // gcd(x, y)

tmp = A[0]
for i in range(1, N):
  tmp = lcm(A[i], tmp)
#print(tmp)

answer = 0
for a in A:
  answer += tmp // a
print(answer % MOD)
### BUGGY CODE ###

def nCr(n, r):
    r = min(r, n-r)

    X = 1
    for i in range(n, n-r, -1):
        X *= i

    Y = 1
    for i in range(r, 1, -1):
        Y *= i

    return X//Y

N = int(input())
A = list(map(int, input().split()))
B = [0]
t = 0
for i in range(N):
    B.append(B[i] + A[i])

C = set(B)
for j in C:
    count = B.count(j)
    if count > 1:
        t += nCr(count,2)

print(t)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
t = 0
x = 0
B[0] = 1
for i in A:
    x += i
    t += B.get(x, 0)
    B[x] = B.get(x, 0) + 1

print(t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
B = [list(map(int, input().split())) for _ in range(h)]
M = 100*(h*w)
dp = [[0]*w for i in range(h)]
d = abs(A[0][0] - B[0][0])
dp[0][0] |= 1 << (M-d)
dp[0][0] |= 1 << (M+d)
for i in range(h):
  for j in range(w):
    d = abs(A[i][j] - B[i][j])
    if i:
      dp[i][j] |= (dp[i-1][j] << d) & ((1 << (2*M)) - 1)
      dp[i][j] |= dp[i-1][j] >> d
    if j:
      dp[i][j] |= (dp[i][j-1] << d) & ((1 << (2*M)) - 1)
      dp[i][j] |= dp[i][j-1] >> d
t = dp[-1][-1] >> M
ans = (t & (-t)).bit_length() - 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  A = [list(map(int, input().split())) for _ in range(h)]
  B = [list(map(int, input().split())) for _ in range(h)]
  M = 80*(h+w)
  dp = [[0]*w for i in range(h)]
  d = abs(A[0][0] - B[0][0])
  mask = (1 << (2*M)) - 1
  dp[0][0] |= 1 << (M-d)
  dp[0][0] |= 1 << (M+d)
  for i in range(h):
    for j in range(w):
      d = abs(A[i][j] - B[i][j])
      if i:
        dp[i][j] |= (dp[i-1][j] << d) & mask
        dp[i][j] |= dp[i-1][j] >> d
      if j:
        dp[i][j] |= (dp[i][j-1] << d) & mask
        dp[i][j] |= dp[i][j-1] >> d
  t = dp[-1][-1] >> M
  ans = (t & (-t)).bit_length() - 1
  print(ans)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n = int(input())
set0=set([0])
set1 =set()
from collections import deque
ls = deque([])
for _ in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))

ans = [-1] * n
ans[0] = 0
while ls:
    u, v, w = ls.popleft()
    if w == 0: # same
        if u in set0 or v in set0:
            set0 |= set([u, v])
            ans[u]=0
            ans[v]=0
        elif u in set1 or v in set1:
            set1 |= set([u, v])
            ans[u] = 1
            ans[v] = 1
        else:
            ls.append((u, v, w))
    else:#different
        if u in set0:
            set1.add(v)
            ans[v] =1
        elif v in set0:
            set1.add(u)
            ans[u] =1
        elif v in set1:
            set0.add(u)
            ans[u] =0
        elif u in set1:
            set0.add(v)
            ans[v] =0
        else:
            ls.append((u, v, w))

for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
explored = set()
next = [[]for _ in range(n)]

from collections import deque
ls = []
for i in range(n-1):
    u, v, w= map(int, input().split())
    ls.append((u-1, v-1, w%2))
    next[u-1].append((v-1, w%2))
    next[v-1].append((u-1, w%2))

ans = [-1] * n

exploring = deque()
next_que = deque([0])
ans[0]=0
explored.add(0)
while next_que:
    i = next_que.popleft()
    exploring.extend(next[i])
    while exploring:
        a, b = exploring.popleft()
        ans[a] = (ans[i]+b)%2
        list = next[a]
        if a not in explored:
            next_que.append(a)
        explored.add(a)


for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
np_a = np.array(A)

ng = []

for a in A:
    # 自分は必ず割り切れる 他にいたら 0が2以上になるはず
    if Counter(a % np_a)[0] > 1:
        ng.append(a)

print(N - len(ng))


### FIXED CODE ###

import numpy as np
from collections import Counter
from math import sqrt
from time import time


def main():
    N = int(input())
    np_a_o = list([int(x) for x in input().split()])
    np_a = Counter(np_a_o)

    np_a_keys = set(np_a.keys())

    div_list = set()
    key_max = max(np_a_keys)

    c = 0

    for key in np_a_keys:
        for div in range(key*2, key_max+1, key):
            div_list.add(div)

    r = np_a_keys - div_list

    u, count = np.unique(np.array(np_a_o), return_counts=True)
    r -= set(u[count > 1])

    print(len(r))


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

import copy
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  aa=copy.copy(a)
  del aa[i]
  ans=0
  temp=0
  for j in range(n-1):
    ans=ans+abs(aa[j]-temp)
    temp=aa[j]
  print(ans+abs(temp))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
temp=0
for i in range(n):
  ans=ans+abs(a[i]-temp)
  temp=a[i]
ans=ans+abs(temp)
a.insert(0,0)
a.append(0)
for i in range(1,n+1):
  print(ans-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]))
### BUGGY CODE ###

s=input()
q=int(input())
n=0
for i in range(q):
    li=input().split()
    if int(li[0])==1:
        n+=1
    elif int(li[0])==2:
        if (n+int(li[1]))%2==1:
            s=li[2]+s
        else:
            s=s+li[2]
if n%2==0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
n=0
que=deque(s)
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            que.appendleft(l[4])
        else:
            que.append(l[4])

ans=''.join(que)
if n%2==0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
li = [-int(i) for i in input().split()]

for _ in range(m):
	heapq.heapify(li) 
	x = heapq.heappop(li)
	if x % 2 == 0:
		heapq.heappush(li, x // 2)
	else:
		heapq.heappush(li, x // 2 + 1)
print(-sum(list(li)))



### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
li = [-int(i) for i in input().split()]
li = sorted(li)

for _ in range(m):
	x = heapq.heappop(li)
	#print(x)
	if x % 2 == 0:
		heapq.heappush(li, x // 2)
	else:
		heapq.heappush(li, x // 2 + 1)
	#print(li)
print(-sum(list(li)))
### BUGGY CODE ###

n,k = map(int,input().split())
r = (n-1)*(n-2)//2 - k
if r < 0:
  print(-1)
else:
  print(n-1+r)
  for i in range(1,n):
    print(1,i+1)
  while r != 0:
    for i in range(1,n):
      while r != 0:
        for j in range(i+1,n):
          print(i+1,j+1)
          r -= 1

### FIXED CODE ###

n,k = map(int,input().split())
r = (n-1)*(n-2)//2 - k
if r < 0:
  print(-1)
else:
  print(n-1+r)
  for i in range(1,n):
    print(1,i+1)
  for i in range(1,n):
    r -= n-i-1
    if r >= 0:
      for j in range(i+1,n):
        print(i+1,j+1)
    else:
      for j in range(i+1,r+n):
        print(i+1,j+1)
      break
### BUGGY CODE ###

def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_hw = [[] for _ in range(h+1)]

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_hw[h].append(w)

m_h = max(l_h)
m_w = max(l_w)

ans = m_h + m_w

l_h_2 = my_index_multi(l_h,m_h)
l_w_2 = my_index_multi(l_w,m_w)

flag = False

for i in l_h_2:
    for j in l_w_2:
        if j not in l_hw[i]:
            flag = True
            break
    if flag:
        break
else:
    ans -= 1

print(ans)

### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def my_index_multi(l, x):
    return [k for k, _x in enumerate(l) if _x == x]

h,w,m = map(int,input().split())
l_h = [0]*(h+1)
l_w = [0]*(w+1)
l_b = set()

for _ in range(m):
    h,w = map(int,input().split())
    l_h[h] += 1
    l_w[w] += 1
    l_b.add((h,w))

m_h = max(l_h)
m_w = max(l_w)

l_h_2 = []
for i, x in enumerate(l_h):
    if x == m_h:
        l_h_2.append(i)

l_w_2 = []
for i, x in enumerate(l_w):
    if x == m_w:
        l_w_2.append(i)

ans = m_h + m_w

for i,j in itertools.product(l_h_2,l_w_2):
    if (i,j) not in l_b:
        break
else:
    ans -= 1

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

import bisect

A,B,Q=map(int,input().split())
slist = []
for i in range(A):
  slist.append(int(input()))
#print(slist)
  
tlist = []
for i in range(B):
  tlist.append(int(input()))
#print(tlist)

for i in range(Q):
  x = int(input())
  min_dist = 10**11
  
  # x->s->t
  sl = bisect.bisect(slist,x)
  if sl == 0:
    si = [0]
  elif sl == len(slist):
    si = [sl-1]
  else:
    si = [sl-1,sl]
  
  for index in si:
    s = slist[index]
    dist = abs(x-s)

    tl = bisect.bisect(tlist,s)
    if tl == 0:
      dist += abs(s-tlist[0])
    elif tl == len(tlist):
      dist += abs(s-tlist[len(tlist)-1])
    else:
      dist += min(abs(s-tlist[tl-1]),abs(s-tlist[tl]))
    
    if dist < min_dist:
      min_dist = dist

  # x->t->s
  tl = bisect.bisect(tlist,x)
  if tl == 0:
    ti = [0]
  elif tl == len(tlist):
    ti = [tl-1]
  else:
    ti = [tl-1,tl]
  
  for index in ti:
    t = tlist[index]
    dist = abs(x-t)

    sl = bisect.bisect(slist,t)
    if sl == 0:
      dist += abs(t-slist[0])
    elif sl == len(slist):
      dist += abs(t-slist[len(slist)-1])
    else:
      dist += min(abs(t-slist[sl-1]),abs(t-slist[sl]))
    
    if dist < min_dist:
      min_dist = dist

  print(min_dist)


### FIXED CODE ###

import bisect

A,B,Q=map(int,input().split())
slist = []
for i in range(A):
  slist.append(int(input()))
#print(slist)

tlist = []
for i in range(B):
  tlist.append(int(input()))
#print(tlist)

for i in range(Q):
  x = int(input())
  min_dist = 10**11
  
  # x->s->t
  if x < slist[0]:
    si = [0]
  elif slist[-1] < x:
    si = [len(slist)-1]
  else:
    sl = bisect.bisect(slist,x)
    si = [sl-1,sl]
    
  for index in si:
    s = slist[index]
    dist = abs(x-s)

    if s < tlist[0]:
      dist += tlist[0]-s
    elif tlist[-1] < s:
      dist += s-tlist[-1]
    else:
      tl = bisect.bisect(tlist,s)  
      dist += min(s-tlist[tl-1],tlist[tl]-s)
    
    if dist < min_dist:
      min_dist = dist

  # x->t->s
  if x < tlist[0]:
    ti = [0]
  elif tlist[-1] < x:
    ti = [len(tlist)-1]
  else:
    tl = bisect.bisect(tlist,x)
    ti = [tl-1,tl]
    
  for index in ti:
    t = tlist[index]
    dist = abs(x-t)

    if t < slist[0]:
      dist += slist[0]-t
    elif slist[-1] < t:
      dist += t-slist[-1]
    else:
      sl = bisect.bisect(slist,t)
      dist += min(t-slist[sl-1],slist[sl]-t)
    
    if dist < min_dist:
      min_dist = dist

  print(min_dist)
### BUGGY CODE ###

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    
k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(gcd(a,b),c)
print(ans)


### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    
k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(gcd(a,b),c)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans*=min(t[i+1],a[i+1])
print(ans%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans=(ans*(min(t[i+1],a[i+1])))%(10**9+7)
print(ans)
### BUGGY CODE ###

h,n=map(int,input().split())
A=[]; dp=[pow(10,9)]*(h+10)
for i in range(n):
  x,y=map(int,input().split())
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h):
    if dp[i]==pow(10,9): continue
    index=min(h,i+a)
    dp[index]=min(dp[index],dp[i]+b)
print(dp[h])

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)