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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
way = [[] for _ in range(n+1)]
for i in range(m):
    a,b = inpm()
    way[a].append(b)
    way[b].append(a)

ans = [0 for i in range(n+1)]
q = queue.Queue()
q.put((1,0))
while not q.empty():
    room,sign = q.get()
    if ans[room] != 0:
        continue
    ans[room] = sign

    for i in way[room]:
        q.put((i,room))

print('Yes')
for i in range(2,n+1):
    print(ans[i])
### BUGGY CODE ###


import collections
n,ais = int(raw_input()), map(int, raw_input().split())
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque([0])
h = {0:[2,1,0], 1:[1], 2:[0]} 
while(n):
	booll = False
	for u in h[q[-1]] + [-1]:
		if u == -1:
			boool = True
			break
		if cc[u]:
			q.append(u)
			cc[u] -=1
			n -=1
			break
	if booll:
		break

print 'Yes' if n == 0 else 'No'

### FIXED CODE ###


n,ais = int(raw_input()), map(int, raw_input().split())
import collections
cc = collections.Counter()
for ai in ais:
	if ai % 4 == 0: cc[0] += 1
	elif ai % 2 == 0: cc[1] += 1
	else: cc[2] += 1

q = collections.deque()
while(n):
	if len(q) == 0:
		for u in range(3)[::-1]:
			if cc[u] > 0:
				q.append(u)
				cc[u]-=1
				n -=1
				break
		if len(q) == 0: break
	else:
		if q[-1] == 0:
			if cc[2]:
				q.append(2)
				cc[2]-=1
				n-=1
			elif cc[1]:
				q.append(1)
				cc[1]-=1
				n-=1
			elif cc[0]:
				q.append(0)
				cc[0]-=1
				n-=1
			else:
				break
		elif q[-1] == 2:
			if cc[0] == 0:
				break
			else:
				q.append(0)
				cc[0]-=1
				n-=1
		elif q[-1] == 1:
			if cc[1] > 0:
				q.append(1)
				cc[1]-=1
				n-=1
			else:
				break

print 'Yes' if n == 0 else 'No'
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))

for i in range(k):
    akarusanext=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        for k in range(kagen,jogen+1):
            akarusanext[k]+=1
    akarusa=akarusanext
    if akarusa==[n]*n:
        break

for i in range(n):
    print(akarusa[i], end=" ")


### FIXED CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=imos
    for j in range(1,n):
        akarusanext[j]+=akarusanext[j-1]
    
    if akarusa==akarusanext:
        break
    else:
        akarusa=akarusanext

for i in range(n):
    print(akarusa[i], end=" ")
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

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


N = int(input())


def g(x, y, z):
    return (x + y + z) ** 2 - (x*y + y*z + z*x)


# for x in range(1, 20):
#     for y in range(1, 20):
#         for z in range(1, 20):
#             print(g(x, y, z))

for n in range(1, N+1):
    num_dict = {}
    res = 0
    flag = False
    for x in range(1, 30):
        for y in range(1, 30):
            for z in range(1, 30):
                num = g(x, y, z)
                if num > n:
                    # print('break')
                    break
                if num == n:
                    # print(f'{x}+{y}+{z}={num}')
                    if (x, y, z) in num_dict:
                        continue
                    # print('doesnt exist')
                    num_dict[(x, y, z)] = 1
                    res += 1
    print(res)


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

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


N = int(input())


def g(x, y, z):
    return (x + y + z) ** 2 - (x*y + y*z + z*x)


xyz_dict = defaultdict(int)
num_dict = defaultdict(int)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            num = g(x, y, z)
            if (x, y, z) in xyz_dict:
                continue
            xyz_dict[(x, y, z)] = 1
            num_dict[num] += 1


for n in range(1, N+1):
    print(num_dict[n])
### BUGGY CODE ###

s=int(input())
n=len(str(s))
 
ans=0
for L in range(5,n+1):
  for i in range(n-L+1):
    if ((s//(10**(n-L-i)))%(10**L))%2019==0:
      ans+=1
 
print(ans)

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
c,d=0,1
for i in s:
    c+=int(i)*d
    c%=2019
    d*=10
    d%=2019
    a[c]+=1
ans=0
for i in a:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
if n<=x:
    x=n-1
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])


### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[-1]*n
dp[0]=0
if n<=x:
    x=n-1
for i in range(1,x+1):
    dp[i]=abs(a[i]-a[0])

for i in range(x+1,n):
    min1=10**9
    for j in range(i-(x),i):  
        if min1>dp[j]+abs(a[j]-a[i]):               
            min1=dp[j]+abs(a[j]-a[i])
    dp[i]=min1
print(dp[-1])
### BUGGY CODE ###

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

MOD = 1000000007
def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD
mod_inv = lambda x: pow_mod(x, MOD - 2)

a = 0
for i in range(1, n):
  a += (i * (n - i)) % MOD 
  a %= MOD
a *= (m * m) % MOD
a %= MOD

b = 0
for i in range(1, m):
  b += (i * (m - i)) % MOD 
  b %= MOD
b *= (n * n) % MOD
b %= MOD

w = (m * n - 2) % MOD
wCx = {0: 1}
for i in range(1, k+1):
  wCx[i] = wCx[i - 1] 
  wCx[i] *= (w - i + 1) % MOD
  wCx[i] %= MOD
  wCx[i] *= mod_inv(i)
  wCx[i] %= MOD

ans = ((a + b) % MOD) 
ans *= wCx[k-2]
ans %= MOD

print(ans)

### FIXED CODE ###

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

MOD = 1000000007
def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD
mod_inv = lambda x: pow_mod(x, MOD - 2)

a = 0
for i in range(1, n):
  a += (i * (n - i)) % MOD 
  a %= MOD
a *= (m * m) % MOD
a %= MOD

b = 0
for i in range(1, m):
  b += (i * (m - i)) % MOD 
  b %= MOD
b *= (n * n) % MOD
b %= MOD

w = (m * n - 2) % MOD
u = 1
v = 1
for i in range(1, k-1):
  u *= (w - i + 1)
  u %= MOD
  v *= i
  v %= MOD

ans = ((a + b) % MOD) 
ans *= u
ans %= MOD
ans *= mod_inv(v)
ans %= MOD


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

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

dic = dict()
for i in a:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

cnt = 0
dic_v = list(dic.values())
for i in range(len(dic_v)):
    x = dic_v[i]
    cnt += int(x*(x-1)/2)
    
def count(k):
    cnt = -1
    for i in range(n):
        if a[i] == a[k]:
            cnt += 1
    return cnt

for k in range(n):
    print(cnt - count(k))

### FIXED CODE ###

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

dic = dict()
for i in a:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

cnt = 0
dic_v = list(dic.values())
for i in range(len(dic_v)):
    x = dic_v[i]
    cnt += int(x*(x-1)/2)
    
for k in range(n):
    print(cnt - (dic[a[k]]-1))
### BUGGY CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*(2**i)
    ans %= mod
print(ans)


### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int, list(input())))
#print(X)

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b*A[-i-1]
    b *= 2
  return r

for i in range(N):
  A = X.copy()
  A[i] ^= 1
#  print(A)
  n = num(A)
#  print(n)
  call = 0
  if n > 0:
    f(n)
  print(call)


### FIXED CODE ###

N = int(input())
X = input()
B = X.count('1')
#print(B, 'B')

base_mod_1 = [1 for i in range(N)] # 2^i mod B+1
if B > 1:
  base_mod_2 = [1 for i in range(N)] # 2^i mod B-1

for i in range(1, N):
  base_mod_1[i] = (base_mod_1[i-1] * 2) % (B+1)
  if B > 1:
    base_mod_2[i] = (base_mod_2[i-1] * 2) % (B-1)

def num(A):
  b = 1
  r = 0
  for i in range(len(A)):
    r += b * int(A[-i-1])
    b *= 2
  return r

def f(n):
  global call
  call += 1
  bit = 0
  m = n
  while m > 0:
    if m % 2 == 1:
      bit += 1
    m //= 2
  next_n = n % bit
  if next_n > 0:
    f(next_n)

x = num(X)
x1 = x % (B+1)
if B > 1:
  x2 = x % (B-1)
#print('x', len(X))

for i in range(N):
  call = 0
  if X[i] == '0':
    y = (x1 + base_mod_1[-i-1]) % (B+1)
    R = B + 1
    call = 1
  else:
    if B > 1:
      y = (x2 - base_mod_2[-i-1]) % (B-1)
      R = B - 1
      call = 1
    else:
      y = 0
#  print(y, '+', call)
  if y > 0:
    f(y)
  print(call)
### BUGGY CODE ###

n=input()
a=list(map(int,input().split()))
result=[]
for item in a:
  result.append(item)
  result=result[::-1]

print(*result)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=a[::-2]+a[N%2::2]
print(*b)
### BUGGY CODE ###

n=int(input())+1
print(sum(sum(range(i,n,i))for i in range(1,n)))

### FIXED CODE ###

n=int(input())+1
print(sum(sum(range(i,n,i))for i in range(1,n)))
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ai=0
bi=0
if sum(a)+sum(b)<k:print(n+m);exit()
ma=0
for x in range(len(a)+1):
    sa=sum(a[:x])
    for y in range(len(b)+1):
        if sa+sum(b[:y])>k:break
        ma=max(ma,x+y)
print(ma)

### FIXED CODE ###

import itertools
import bisect

n,m,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=list(map(int,input().split()))
aa=list(itertools.accumulate(a))
bb=list(itertools.accumulate(b))
r=0
for i,ax in enumerate(aa):
    bis=bisect.bisect_right(bb,k-ax)
    if bis==0 and ax>k:continue
    r=max(r,i+bis)
print(r)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
for B, C in BC:
    A.sort()
    mn = A[0]
    if mn >= C:
        break
    if A[B - 1] <= C:
        A[:B] = [C] * B
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i + 1
            else:
                a = i
        A[:b] = [C] * b

print(sum(A))

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, N
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r - 1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
        B = n - l
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))
### BUGGY CODE ###

size,init,query= list(map(int,input().split()))
health = []
ans = []
for i in range(size):
    health.append(init)
for i in range(query):
    attack = int(input())
    for i in range(0,len(health)):
        health[i] -= 1
    health[attack-1] += 1
for i in health:
    if i<1:
        ans.append('No')
    else:
        ans.append('Yes')
for i in ans:
    print(i)

### FIXED CODE ###

n, k, q = map(int, input().split())
# a = []
point = [k-q] * n
for i in range(q):
    input_num = int(input())
    point[input_num - 1] += 1
    # a.append(input_num)
 
for i in range(n):
    if point[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.append(0)
L.sort(reverse=True)
t=0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]<L[j]+L[k]:
                t+=1

print(t)


### FIXED CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        c=bisect_left(L,l)
        ans+=max(0,c-j-1)
print(ans)
### BUGGY CODE ###

# D - RGB Triplets
N = int(input())
S = input()
R = []
G = []
B = []
RG = []
GB = []
BR = []
ans = 0
for i in range(N):
    if S[i]=='R':
        R.append(i)
        for j in G:
            RG.append([j,i])
        for j in B:
            BR.append([j,i])
        for j,k in GB:
            if k-j!=i-k:
                ans += 1
    elif S[i]=='G':
        G.append(i)
        for j in B:
            GB.append([j,i])
        for j in R:
            RG.append([j,i])
        for j,k in BR:
            if k-j!=i-k:
                ans += 1
    else:
        B.append(i)
        for j in R:
            BR.append([j,i])
        for j in G:
            GB.append([j,i])
        for j,k in RG:
            if k-j!=i-k:
                ans += 1
print(ans)

### FIXED CODE ###

# D - RGB Triplets
N = int(input())
S = input()
r,b,g = 0,0,0
for i in range(N):
    if S[i]=='R':
        r += 1
    elif S[i]=='G':
        g += 1
    else:
        b += 1
ans = r*g*b
for i in range(N):
    for j in range(i+1,N):
        k = 2*j-i
        if k<N and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import math
#最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#因数分解
def factorize(x):
    ans=1#約数１
    div=2
    flag=0
    while div<=x:
        while x%div==0:
            x=x//div
            flag=1
        if flag==1:
            ans+=1
        div+=1
        flag=0
    return ans

a,b=map(int,input().split())
g=gcd(a,b)
f=factorize(g)
print(f)


### FIXED CODE ###

import math
#最大公約数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
#因数分解
def factorize(x):
    f=[]
    div=2
    while div**2<=x:
        while x%div==0:
            f.append(div)
            x=x//div
        div+=1
    if x>1:
        f.append(x)
    return f

"""def factorize(x):
    ans=1#約数１
    div=2
    while div**2<=x:
        while x%div==0:
            x=x//div
            flag=1
        if flag==1:
            ans+=1
        div+=1
        flag=0
    if x>1:
        ans+=1
    return ans"""

a,b=map(int,input().split())
g=gcd(a,b)
f=factorize(g)
print(len(set(f))+1)
### BUGGY CODE ###

import fractions
import numpy as np
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
A =np.array(A)
ans = np.sum(a//A)
print(ans%MOD)

### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)
### BUGGY CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sl()
    qu = collections.deque(A)
    ret = []
    re = False
    for q in qu:
        if re:
            ret.append(q)
            ret = ret[::-1]
            re = False
        else:
            ret.append(q)
            ret = ret[::-1]
            re = True
    print(' '.join(ret))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ret = collections.deque()

    for n in range(N):
        if N % 2 == (n+1) % 2:
            ret.appendleft(A[n])
        else:
            ret.append(A[n])
    print(*ret)


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

N, M= map(int, input().split())
zahyo = []
for i in map(int,input().split()):
    zahyo += [i]
sum=0
for i in range(M-1):
    for j in range(M):
        if i < j:
            if zahyo[i] > zahyo[j]:
                a = zahyo[i]
                zahyo[i] = zahyo[j]
                zahyo[j] = a
gap = []
for i in range(M-1):
    gap += [zahyo[i+1]-zahyo[i]] 
for i in range(M-2):
    for j in range(M-1):
        if i < j:
            if gap[i] < gap[j]:
                a = gap[i]
                gap[i] = gap[j]
                gap[j] = a
if N >= M:
    print(0)
elif N == 1:
    print(zahyo[M-1] - zahyo[0])
else:
    for i in gap[N-1:]:
        sum += i
    print(sum)

### FIXED CODE ###

N, M= map(int, input().split())
zahyo = []
for i in map(int,input().split()):
    zahyo += [i]
sum=0
#マージソート用関数
# merge(p, q): あらかじめソートされた配列 p と q をまとめる。
def merge(p,q):
    result=[]
    i,j=0,0
    #p[i]とq[j]を比べて小さい方をresultに加える。
    while i<len(p) and j<len(q):
        #.appendで加える。小さかった方の数字を一つ進める。
        #これで小さいものから順にresultに加えることができる。
        if p[i] <= q[j]:
            result.append(p[i])
            i+=1
        else:
            result.append(q[j])
            j+=1

    #片方の配列が全て比較済みとなると、そこで上のwhile分は終了してしまう
    #なのでまだ比較していない要素が残っている配列をそのままresultに連結する
    #これは.extendを使う。まだ比較していない要素はスライスで簡単に分けることができる。
    if i<len(p):
        result.extend(p[i:])
    if j<len(q):
        result.extend(q[j:])
    #resultを返して終了
    return result

# mergesort(a): 配列 a をマージソートしたものを返す。
def mergesort(a):
    #要素が一つになるまで分割したらそれ自体を返す。
    if len(a)==1:
        return a
    #最初の半分を切り取ってソート
    p=mergesort(a[:len(a)//2])
    #残りの半分を切り取ってソート
    q=mergesort(a[len(a)//2:])
    #merge関数で連結させる
    return merge(p,q)

if M==1:
    print(0)
else:
    zahyo = mergesort(zahyo)
    gap = []
    for i in range(M-1):
        gap += [zahyo[i+1]-zahyo[i]] 
    gap = mergesort(gap)
    if N >= M:
        print(0)
    else:
        for i in gap[:M-N]:
            sum += i
        print(sum)
### BUGGY CODE ###

N = int(input())
ll = list(map(int, input().split(" ")))
# print(N)
# print(ll)


def ni(i):
    return int(bin(i)[2:])


for i in range(N):
    ll[i] = ni(ll[i])

# print(ll)

count = 0
for i in range(N):
    for j in range(i, N):
        l = i
        r = j
        # print(i, j)
        sum_num = str(sum(ll[i:j+1]))
        # print(sum_num)
        if "2" not in sum_num:
            # print("yes")
            count += 1
        else:
            break

print(count)




### FIXED CODE ###

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

l, r = 0, 0
sum_a = 0
ans = 0
while r < n:
    # 右端を進める
    if sum_a & a[r] == 0:
        sum_a += a[r]
        r += 1
        ans += r - l
    # 右端と左端を進める
    elif l == r:
        l += 1
        r += 1
    # 左端を進める
    else:
        sum_a -= a[l]
        l += 1
    # print('l={}, r={}, size={}, ans={}, {}'.format(l, r, r - l, ans, a[l:r]))
print(ans)
### BUGGY CODE ###

import math

def third(n,q):
    n = int(n)
    q = float(q)
    if n == 1: return q/2
    else : return third(n-1,q)- (third(n-1,q)**3-q)/(3*third(n-1,q)**2)

kai = []
while(True):
    try:
        q = input()
        if q == -1:
            for ka in kai:
                print ka
            break
        elif q != -1 :
            n = 1
            q = float(q)
            while  (math.fabs(q-third(n, q)**3) >= 0.00001*q):
                n += 1
            kai.append(third(n, q))
    except EOFError:
        break

### FIXED CODE ###

while(True):
    try:
        q = input()
        if q == -1:
            break
        else :
            q = float(q)
            x = q/2
            while  (abs(q-x**3) >= 0.00001*q):
                x = x- (x**3-q)/(3*x**2)
            print '{:.6f}'.format(x)
    except EOFError:
        break
### BUGGY CODE ###

n=int(input())
p=1
for i in range(1,n+1):
  p=p*i
  while p>1000000007:
    p=p-1000000007
print(p%1000000007)

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))