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

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


ans = 0
for i in range(n - k + 1):
    f = a[-(i + 1)] - a[i]
    cnt = binomial_coefficient(n - i - 1, k - 1)
    ans += f * cnt
    ans %= mod

print(ans % mod)


### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7

fac = [i for i in range(N + 1)]
for i in range(2, N + 1):
    fac[i] *= fac[i - 1]
    fac[i] %= mod
fac[0] = 1

fk = pow(fac[K - 1], mod-2, mod)

ans = 0
for i in range(N - K + 1):
    f = a[-(i + 1)] - a[i]
    nCr = fac[N - i - 1]*pow(fac[N-K-i], mod-2, mod)*fk % mod
    ans += f * nCr
    ans %= mod

print(ans % mod)
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = map(int, input().split())
d = [[-1]*W for i in range(H)]
#temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    #max = 0
    #dx = [1, 0, -1, 0]
    #dy = [0, 1, 0, -1]

    #que = deque([])
    s = 0
    while black_cells:
        p, q = black_cells.popleft()
        s = d[p][q]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = q + dx
            ny = p + dy
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                #que.append((nx))
                #temp[ny][nx] = d[p[0]][p[1]] + 1
                #a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                #if a < d[ny][nx]:
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return s






#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)


### FIXED CODE ###

from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

def main():
    n = int(input())
    s = [sorted(input()) for i in range(n)]
    cnt = 0
    s.sort()
    sb = []
    while s:
        sa = s.pop()
        cnt += s.count(sa) 
        if sa == sb:
            cnt + 1
        sb = sa
    print(cnt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    dic = {}
    cnt = 0

    for i in s:
        if i in dic:
            cnt+=dic[i]
            dic[i]+=1
        else:
            dic[i]=1

    print(cnt)

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

n,q = map(int, input().split())
s = input()
for i in range(q):
  l,r = map(int,input().split())
  print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
c = []
pre = ""
count = 0
for i in range(n):
  if pre == "A" and s[i] == "C":
    count += 1
  pre = s[i]
  c.append(count)
  
for i in range(q):
  l,r = map(int,input().split())
  print(c[r-1]-c[l-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[[0]*4 for _ in range(n+1)]
# 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
# x0=n-x1-x2-x3
from collections import Counter
a.append(1)
a.append(2)
a.append(3)
ca=dict(Counter(a))
import sys
sys.setrecursionlimit(10**7)
memo={}
memo[(0,0,0)]=0
def func(x1,x2,x3):
    if (x1,x2,x3) in memo:return memo[(x1,x2,x3)]
    ret=0
    s=x1+x2+x3
    if x1>0:ret+=((n/s)+func(x1-1,x2,x3))*(x1/s)
    if x2>0:ret+=((n/s)+func(x1+1,x2-1,x3))*(x2/s)
    if x3>0:ret+=((n/s)+func(x1,x2+1,x3-1))*(x3/s)
    #print(x1,x2,x3,ret)
    memo[(x1,x2,x3)]=ret
    return ret
print(func(ca[1]-1,ca[2]-1,ca[3]-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
    # x0=n-x1-x2-x3
    ca={1:a.count(1),2:a.count(2),3:a.count(3)}
    memo=[[[-1]*(n+2) for _ in range(n+2)] for _ in range(n+2)]
    memo[0][0][0]=0
    for x3 in range(ca[3]+1):
        for x2 in range(ca[2]+ca[3]+1-x3):
            for x1 in range(ca[1]+ca[2]+ca[3]+1-x3-x2):
                if (x1,x2,x3)==(0,0,0):continue
                tmp=0
                if x1>0:tmp+=memo[x1-1][x2][x3]*x1
                if x2>0:tmp+=memo[x1+1][x2-1][x3]*x2
                if x3>0:tmp+=memo[x1][x2+1][x3-1]*x3
                tmp+=n
                tmp/=x1+x2+x3
                memo[x1][x2][x3]=tmp
    print(memo[ca[1]][ca[2]][ca[3]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

#38 B - Problem Set
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

result = 'YES'
for t in T:
    if not(t in D):
        result = 'NO'
        break
    D.remove(t)
print(result)

### FIXED CODE ###

#38 B - Problem Set
import collections
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

cntD = collections.Counter(D)
cntT = collections.Counter(T)

result = 'YES'
for t in cntT.keys():
    if not(t in cntD):
        result = 'NO'
        break
    if cntT[t] > cntD[t]:
        result = 'NO'
        break
print(result)
### BUGGY CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[-1]] + [0]*3

for i, s in enumerate(S[-2::-1]):
  if s == "?":
    l = [(sum([l[(k-j*10**(i+1))%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[(k-int(s)*10**(i+1))%13] for k in range(13)]
  #print(l)
print(l[5])         

### FIXED CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    while True:
      mid = (l+r)//2
      if a > 0:
        if r - l <=1:
          return r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          l = mid
        else:
          r = mid
      else:
        if r - l <=1:
          return n - r - (1 if a**2 <= x else 0)
        if a * As[mid] <= x:
          r = mid
        else:
          l = mid

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      tot = sum([count(-1, n, A, mid) for A in As]) // 2
      if tot < k:
        l = mid
      else:
        r = mid
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=np.uint32)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
for i in range(q):
    p, q = map(int, input().split())
    mat2 = mat[p-1:q, p-1:q]
    print(np.sum(mat2))

### FIXED CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=int)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        a+=1
        if p in man:break
    print(man.index(max(man)))        

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

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

score = 1
for i in range(K):
    score *= A[i]
pre_score = score
for i in range(K, N):
    score = score / A[i-K] * A[i]
    if score > pre_score:
        print('Yes')
    else:
        print('No')
    pre_score = score

### FIXED CODE ###

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

for i in range(K, N):
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A, B, C = [sorted(list(map(int,input().split())),reverse=True) for _ in range(3)]
ans_list = []
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      if i*j*k > K: break
      else: ans_list.append(A[i]+B[j]+C[k])
[print(ans) for ans in sorted(ans_list,reverse=True)[:K]]

### FIXED CODE ###

import heapq

X,Y,Z,K = map(int,input().split())
A, B, C = [sorted(list(map(int,input().split())),reverse=True) for _ in range(3)]

Q = []
heapq.heappush(Q, [-(A[0]+B[0]+C[0]),0,0,0])
for _ in range(K):
  p, i, j, k = heapq.heappop(Q)
  print(-p)
  if i+1<X and [-(A[i+1]+B[j]+C[k]),i+1,j,k] not in Q: heapq.heappush(Q, [-(A[i+1]+B[j]+C[k]),i+1,j,k])
  if j+1<Y and [-(A[i]+B[j+1]+C[k]),i,j+1,k] not in Q: heapq.heappush(Q, [-(A[i]+B[j+1]+C[k]),i,j+1,k])
  if k+1<Z and [-(A[i]+B[j]+C[k+1]),i,j,k+1] not in Q: heapq.heappush(Q, [-(A[i]+B[j]+C[k+1]),i,j,k+1])
### BUGGY CODE ###

n=int(input())
s=input()
set_n_3=set()
for i0 in range(n):
    for i1 in range(i0+1,n):
        for i2 in range(i1+1,n):
            set_n_3.add(s[i0]+s[i1]+s[i2])
print(len(set_n_3))

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            flag=[0,0,0]
            for index in range(n):
                if flag[0]==0 and flag[1]==0 and  s[index]==str(i):
                    flag[0]=1
                elif flag[0]==1 and flag[1]==0 and s[index]==str(j):
                    flag[1]=1
                elif flag[0]==1 and flag[1]==1 and s[index]==str(k):
                    ans+=1
#                     print(i,j,k)
                    break
                else:
                    continue
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * (W + 1)
for n in range(N):
	w, v = WV[n]
	for sumw in range(W, -1, -1):
		if sumw + w <= W:
			dp[sumw + w] = max(dp[sumw + w], dp[sumw] + v)
	#for x in dp:
	#	print("{:4d}".format(x), end="")
	#print()
print(max(dp))


### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

h, w, d = map(int, input().split())
xys = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(q)]

dict_ = {v:(x, y) for y, row in enumerate(xys) for x, v in enumerate(row)}

def jump_cost(xy, ab):
    x, y = dict_[xy]
    a, b = dict_[ab]
    return abs(x-a) + abs(y-b)

for l, r in lrs:
    print(sum(jump_cost(xy, ab) for xy, ab in zip(range(l, r+1, d), range(l+d, r+1, d))))

### FIXED CODE ###

from itertools import accumulate

h, w, d = map(int, input().split())
xys = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(q)]

dict_ = {v:(x, y) for y, row in enumerate(xys) for x, v in enumerate(row)}
def jump_cost(xy, ab):
    x, y = dict_[xy]
    a, b = dict_[ab]
    return abs(x-a) + abs(y-b)

m = h * w
d_ = {}
for i in range(1, d+1):
    startend = zip(range(i, m+1, d), range(i+d, m+1, d))
    costs = (jump_cost(xy1, xy2) for xy1, xy2 in startend)
    d_[i % d] = [0] + list(accumulate(costs))

for l, r in lrs:
    a = r // d
    b, c = divmod(l, d)
    print(d_[c][a - (c==0)] - d_[c][b - (c==0)])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, p: "List[int]"):
    max_value = 0
    for i in range(N - K + 1):
        compare_value = sum([p[i + k] for k in range(K)])

        if max_value < compare_value:
            max_value = max(max_value, compare_value)
            index_first = i
        else:
            pass
    # print(max_value)
    # print(index_first)
    result = 0
    for j in range(K):
        result += sum(
            [i / p[index_first + j] for i in range(1, p[index_first + j] + 1)]
        )
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, K: int, p: "List[int]"):
    cumsum = np.cumsum(p)
    # print(cumsum)
    max_value = 0
    index_first = 0
    for i in range(N - K):
        if max_value < cumsum[i + K] - cumsum[i]:
            max_value = max(max_value, cumsum[i + K] - cumsum[i])
            index_first = i + 1

    # print(max_value)
    # print(index_first)
    result = 0
    for j in range(K):
        idm = (p[index_first + j] / 2) * (1 + p[index_first + j])
        idm = idm / p[index_first + j]
        result += idm

    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, p)


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

H, W = map(int, input().split())
S = [list('#' * (W + 2))]
for _ in range(H):
    S.append(list('#' + input() + '#'))
S.append(list('#' * (W + 2)))

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

inf = float('inf')

N = W * H
l = [[inf for _ in range(N)] for _ in range(N)]

for w in range(1, W + 1):
    for h in range(1, H + 1):
        if S[h][w] != '#':
            l[(h - 1) * W + w - 1][(h - 1) * W + w - 1] = 0
            for x, y in zip(dx, dy):
                if S[h + y][w + x] != '#':
                    l[(h - 1) * W + w - 1][(h + y - 1) * W + w + x - 1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            l[i][j] = min(l[i][j], l[i][k] + l[k][j])

ans = -1

for i in range(N):
    for j in range(N):
        k = l[i][j]
        if k != inf:
            ans = max(ans, k)

print(ans)


### FIXED CODE ###

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

inf = float('inf')

import queue

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] != '#':
            q = queue.Queue()
            d = [[inf for _ in range(W)] for _ in range(H)]
            # 距離を保存
            q.put([h, w])
            d[h][w] = 0
            # スタートをキューに、距離を0に
            while not q.empty():
                p = q.get()
                # if p == g:
                #     break
                for i in range(4):
                    nx = p[1] + dx[i]
                    ny = p[0] + dy[i]
                    if nx >= 0 and nx < W and ny >= 0 and ny < H and S[ny][nx] != '#' and d[ny][nx] == inf:
                        q.put([ny, nx])
                        d[ny][nx] = d[p[0]][p[1]] + 1
            for hh in range(H):
                for ww in range(W):
                    if d[hh][ww] != inf:
                        ans = max(ans, d[hh][ww])

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

h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
queries = [list(map(int, input().split())) for _ in range(q)]

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

buf = []
for l, r in queries:
    ans = 0
    l -= 1
    r -= 1
    i, j = c_map[l]
    while l != r:
        i2, j2 = c_map[l + d]
        ans += abs(i - i2) + abs(j - j2)
        l += d
        i, j = i2, j2
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

d_map = [0] * (h * w)
for l in range(h * w - d - 1, -1, -1):
    i, j = c_map[l]
    i2, j2 = c_map[l + d]
    d_map[l] = d_map[l + d] + abs(i - i2) + abs(j - j2)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    buf.append(d_map[l - 1] - d_map[r - 1])

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l,r)] = 0
for p, q in train:
    d[(p-1,q-1)] += 1
for l in range(n):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        add = 0
        for addl in range(l,l+w+1):
            add += d[(addl, l+w)]
        dp[l][l+w] = dp[l][l+w-1] + add
for l, r in quest:
    print(dp[l-1][r-1])


### FIXED CODE ###

n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l+1,r+1)] = 0
for p, q in train:
    d[(p,q)] += 1
for l in range(1,n+1):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        dp[l+1][l+w+1] = dp[l+1][l+w] + dp[l+2][l+w+1] - dp[l+2][l+w] + d[(l+1,l+w+1)]
for l, r in quest:
    print(dp[l][r])
### BUGGY CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
t = []

for i in range(n):
    x = 0
    for j in range(n):
        if j != i:
            x = fractions.gcd(x, a[j])
    t.append(x)

print(max(t))

### FIXED CODE ###

from fractions import gcd

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

left = [0] * (n+1)
right = [0] * (n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for j in range(n-1, -1, -1):
    right[j] = gcd(right[j+1], a[j])
for i in range(n):
    result.append(gcd(left[i], right[i+1]))

print(max(result))
### BUGGY CODE ###

import collections
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=collections.Counter(A).most_common()
print(sum(B[K:][i][1] for i in range(len(B[K:]))))

### FIXED CODE ###

from collections import Counter
N,K=map(int,input().split())
A=input().split()
B=Counter(A)
C=sorted(B.values(),reverse=True)
print(sum(C[K:]))
### BUGGY CODE ###

import math

k = int(input())
cnt = 0

for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            tmp = math.gcd(l,m)
            cnt += math.gcd(tmp,n)
            
print(cnt)

### FIXED CODE ###

#C

import math

k = int(input())
cnt = 0

for i in range(1,k+1):
    for j in range(i,k+1):
        tmp = math.gcd(i,j)
        for l in range(1,k+1):
            if i != j:
                cnt += 2 * math.gcd(tmp,l)
            else:
                cnt += math.gcd(tmp,l)
            
print(cnt)
### BUGGY CODE ###


n = int(input())
s = str(input())
r = []
g = []
b = []


for x in range(n):
    if s[x] == 'R':
        r.append(x+1)
        continue
    if s[x] == 'G':
        g.append(x+1)
        continue
    if s[x] == 'B':
        b.append(x+1)
        continue

def count(x,y,z):
    c = 0
    for i in x:
        for j in y:
            if i > j: continue 
            for k in z:
                if j > k: continue 
                if j - i != k - j:
                    c += 1
    return c

ans = 0
ans += count(r,g,b)
ans += count(r,b,g)
ans += count(b,r,g)
ans += count(b,g,r)
ans += count(g,r,b)
ans += count(g,b,r)

print(ans)

### FIXED CODE ###


def main():
    n = int(input())
    s = str(input())
    cnt = 0
    r = s.count('R')
    g = s.count('G')
    b = s.count('B')

    for i in range(n):
        for j in range(i,n):
            if i == j:
                continue
            k = 2 * j - i
            if k > len(s) - 1:
                continue
            if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
                continue

            cnt +=1

    all = r * g * b
    print(all - cnt) 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

inp = input()
a = int(inp.split(" ")[0])
b = int(inp.split(" ")[1])

def compute_lcm(x, y):

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

print(compute_lcm(a,b))

### FIXED CODE ###

inp = input()
a = int(inp.split(" ")[0])
b = int(inp.split(" ")[1])

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

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

print(lcm(a,b))