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

def union_set(x, y):
    lx, x_set = x
    ly, y_set = y
    l = max(lx, ly)
    if lx == ly:
        z_set = x_set.union(y_set)
    else:
        z_set = x_set if lx > ly else y_set
    return [l, z_set]

def update_set(x, t):
    l, s = x
    return [l + len(t), {si + t for si in list(s)}]

s = input()
t = input()

table = [[0, {''}] for j in range(len(t) + 1)]
table_pre = [[0, {''}] for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = update_set(table_pre[j], si)
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(list(table_pre[-1][1])[0])


### FIXED CODE ###

s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))

def expect_dice(n):
    s = 0
    for i in range(1,n+1):
        s += i
    return s/n 

result = []

for i in range(len(p)-k+1):
    out = 0
    for j in range(i,i+k):
        out += expect_dice(p[j])
    result.append(out)
    
print(max(result))

### FIXED CODE ###

#累積和の利用！！！！！！！！
from itertools import accumulate
n,k = map(int,input().split())
p = list(map(int,input().split()))

m = [(e + 1) / 2 for e in p]
    
m = [0] + m
m = list(accumulate(m))

ans = []
for i in range(n-k+1):
    ans.append(m[i+k] - m[i])
    
print(max(ans))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            ret+=g2(pA,na,x)*2
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        for a in A:
            if a<0:
                ret+=g2(A,a,x)-(1 if a*a<=x else 0)
            else:
                ret+=g1(A,a,x)-(1 if a*a<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

from collections import Counter


n, p = map(int, input().split())
S = reversed(input())

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: int(x) % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
for digit, s in enumerate(S):
    num += int(s) * 10 ** digit
    mod = num % p
    mods.append(mod)

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)


### FIXED CODE ###

from collections import Counter


n, p = map(int, input().split())
S = map(int, reversed(input()))

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: x % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= p
    mods.append(num)
    digit = digit * 10 % p

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
l = [-1]*N
def triplets(n):
  counter = 0
  lower = 1
  upper = round(n**0.5-1)
  for x in range(1, upper+1):
    y_upper = round(0.5*((4*n-3*x**2)**0.5-x))
    for y in range(1, y_upper+1):
      root = (4*n-3*x**2-3*y**2-2*x*y)**0.5
      z = 0.5*(root-x-y)
      if z%1==0 and z>0:
        counter += 1
  return counter
for m in range(1, N+1):
  if l[m-1] == -1:
    tmp = triplets(m)
    l[m-1] = tmp
    if tmp != 0:
      for k in range(2,round((N/m)**0.5)):
        l[m*k**2-1] = tmp
for x in l:
  print(x)

### FIXED CODE ###

N = int(input())
l = [0]*N
upper = round((N-1)**0.5-1)
for x in range(1, upper+1):
    for y in range(1, upper + 1):
        for z in range(1, upper + 1):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if tmp < N+1:
                l[tmp-1]+=1
for x in l:
    print(x)
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        S = S[::-1]
    elif query[0] == '2':
        if query[1] == '1':
            S = query[2] + S
        elif query[1] == '2':
            S = S + query[2]
            
print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S = deque(S)
reverse = False

for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                S.append(C)
            else:
                S.appendleft(C)
        elif F == '2':
            if reverse:
                S.appendleft(C)
            else:
                S.append(C)
            
result = ''.join(S)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

#
from collections import deque

import sys
input = sys.stdin.readline


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()

    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)
    # print(edges)

    s, t = map(int, input().split())

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

    s, t = map(int, input().split())

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


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

from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])

l = []
for i in range(n):
    if not data[i+1].split()[0] in l:
        l.append(data[i+1].split()[0])
print(len(l))

### FIXED CODE ###

from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])

l = []
for i in range(n):
    l.append(data[i+1].split()[0])
print(len(set(l)))
### BUGGY CODE ###

s = list(input())
n = int(input())
head = []
tail = []

cnt = 0
for _ in range(n):
    li = list(input().split())
    if li[0] == '1':
        head, tail = tail, head
        s = s[::-1]
        cnt += 1
    else:
        if li[1] == '1':
            head += li[2]
        else:
            tail += li[2]

ans = head[::-1] + s + tail
print(*ans , sep='')

### FIXED CODE ###

s = list(input())
n = int(input())
head = []
tail = []

cnt = 0
for _ in range(n):
    li = list(input().split())
    if li[0] == '1':
        head, tail = tail, head
        cnt += 1
    else:
        if li[1] == '1':
            head += li[2]
        else:
            tail += li[2]

if cnt % 2 != 0:
    s = s[::-1]
    
ans = head[::-1] + s + tail
print(*ans , sep='')
### BUGGY CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [Counter() for _ in range(MAXBIT)]
for a in A:
    b = format(a, '0'+str(MAXBIT)+'b')
    for d in range(MAXBIT):
        C[d].update([b[d]])
ans = 0
for d in range(MAXBIT):
    ans += (C[d]['0'] * C[d]['1']) * (2 ** (MAXBIT-d-1))
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
MAXBIT = 60
MOD = 10 ** 9 + 7
A = list(map(int, input().split()))
B = []
C = [[] for _ in range(MAXBIT)]
for a in A:
    for d in range(MAXBIT):
        C[d].append(a >> d & 1)
ans = 0
for d in range(MAXBIT):
    num0 = C[d].count(0)
    num1 = N - num0
    ans += ((num0 * num1) % MOD) * pow(2, d, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_prod_lt(x):
    n_prod = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        n_prod += n_partner(i, x)
    return n_prod

# i > jであるjのうち、A[i] * A[j] < xとなるjの数
def n_partner(i, x):
    if A[i] > 0:
        if A[i] * A[i + 1] >= x:
            ans = 0
        elif A[i] * A[n - 1] < x:
            ans = n - 1 - i
        else:
            ok = i + 1
            ng = n - 1
            while ng - ok > 1:
                mid = (ng + ok) // 2
                if A[i] * A[mid] < x:
                    ok = mid
                else:
                    ng = mid
            ans = ok - i
    else:
        if A[i] * A[i + 1] < x:
            ans = n - 1 - i
        elif A[i] * A[n - 1] >= x:
            ans = 0
        else:
            ng = i + 1
            ok = n - 1
            while ok - ng > 1:
                mid = (ng + ok) // 2
                if A[i] * A[mid] < x:
                    ok = mid
                else:
                    ng = mid
            ans = n - 1 - ng
    return(ans)

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_prod_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(20000000)
N, K = map(int, input().split())
heights = [int(h) for h in input().split()]


@lru_cache(None)
def dfs(i):
    if i == len(heights) - 1:
        return 0
    res = float("inf")
    for k in range(1, K + 1):
        if i + k < len(heights):
            res = min(res, abs(heights[i] - heights[i + k]) + dfs(i + k))
    return res


print(dfs(0))


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
 
def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0
 
    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]
 
 
print(frog(n, k, h))
### BUGGY CODE ###

n,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for i in range(n)]
dp=[[0]*110000 for i in range(110)]
#print(dp)

for i in range(1,n+1):
  for j in range(W+1):
    dp[i][j]=dp[i-1][j]
    if j-wv[i-1][0]>=0:
      dp[i][j]=max(dp[i][j],
                   dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
      
print(dp[n][W])

### FIXED CODE ###

N,W=map(int,input().split())
L = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for j in range(110000)] for i in range(110)]
for i in range(1,N+1):
  for j in range(W+1):
    dp[i][j]=dp[i-1][j]
    if j-L[i-1][0]>=0:
      dp[i][j]=max(dp[i][j],dp[i-1][j-L[i-1][0]]+L[i-1][1])
ans=dp[N][W]
print(ans)
### BUGGY CODE ###

import math


def main():
    A, B, N = map(int, input().split())

    def target(x):
        # print(math.floor(A * x / B))
        # print(A * math.floor(x / B))
        return math.floor(A * x / B) - A * math.floor(x / B)

    max_value = -1
    for i in range(1, min(N+1, B + 1)):
        v = target(i)
        # print(f'x={i} f(x)={v}')
        if v > max_value:
            max_value = v
    print(max_value)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main():
    A, B, N = map(int, input().split())

    def target(x):
        # print(math.floor(A * x / B))
        # print(A * math.floor(x / B))
        return math.floor(A * x / B) - A * math.floor(x / B)

    print(target(min(N, B-1)))

    # B_A = 1.0 * B / A
    #
    # max_value = -1
    # for i in range(1, int(B / B_A) + 3):
    #     x = int(B_A * i)+1
    #     if x > N:
    #         break
    #     v = target(x)
    #     # print(f'x={i} f(x)={v}')
    #     if v > max_value:
    #         max_value = v
    #
    #     x_2 = int(B_A * i)
    #     if x_2 > N:
    #         break
    #     v = target(x_2)
    #     # print(f'x={i} f(x)={v}')
    #     if v > max_value:
    #         max_value = v
    #
    #     x_3 = int(B_A * i) -1
    #     if x_3 > N:
    #         break
    #     v = target(x_3)
    #     # print(f'x={i} f(x)={v}')
    #     if v > max_value:
    #         max_value = v
    #
    # print(max_value)


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

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1
 
l = 7000
m = 0
 
M = [[[0] * l for i in range(w)] for j in range(h)]
N = [[0 for i in range(w)] for j in range(h)]
N[0][0] = C[0][0]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1
 
for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1

        N[i+1][j] = max(N[i+1][j], N[i][j] + C[i+1][j])

    if j+1 < w:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1

        N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
 
ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)
### BUGGY CODE ###

from bisect import insort_left
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
for _ in range(M):
    m=A.pop(-1)
    insort_left(A,m//2)
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=tuple(map(int,input().split()))
l=[(-i,i) for i in A]
heapq.heapify(l)
for _ in range(M):
    m=heapq.heappop(l)
    heapq.heappush(l,(-(m[1]//2),m[1]//2))
a=0
for i in l:
    a+=i[1]
print(a)
### BUGGY CODE ###

s,t=input(),input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans+=s[n-1];n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans[::-1])

### FIXED CODE ###

s,t=input(),input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)
### BUGGY CODE ###

N,X,Y = map(int, input().split())
X = X-1
Y = Y-1
kyori  = []
for i in range(N):
    for j in range(i,N):
        l = min(abs(i-j), abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
        kyori.append(l)
for k in range(1,N):
    print(kyori.count(k))

### FIXED CODE ###

N,X,Y = map(int, input().split())
X = X-1
Y = Y-1
kyori  = [0]*N
for i in range(N):
    for j in range(i+1,N):
        l = min(abs(i-j), abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
        kyori[l] += 1
for k in range(1,N):
    print(kyori[k])
### BUGGY CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
l = lcm(b)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)


### FIXED CODE ###

#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
print(total%mod)
### BUGGY CODE ###

N=int(input().strip())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=0
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]>b[j]:
            break
        for k in range(len(c)):
#            print(a[i],b[j],c[k])
            if a[i]>=b[j] or b[j]>=c[k]:
                break
            else:
#                if ans==0:
                ans+=1
#                print(a[i],b[j],c[k])
#                    at=a[i]
#                    bt=b[j]
#                    ct=c[k]
#                    print(at,bt,ct)
#                elif at!=a[i] or bt!=b[j] or ct!=c[k]:
#                    ans+=1
#                    at=a[i]
#                    bt=b[j]
#                    ct=c[k]
#                    print(at,bt,ct)
print(ans)

### FIXED CODE ###

import bisect
N=int(input().strip())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
a.sort()
#b.sort(reverse=True)
c.sort()
ans=0
#for i in range(len(b)):
#    la=bisect.bisect_left(a, b[i])
#    ra=bisect.bisect_right(c, b[i])
#    ans+=la*(len(c)-ra)
#    print(la,(len(c)-ra))


for i in range(len(b)):
    la=bisect.bisect_left(a, b[i])
    ra=bisect.bisect_right(c, b[i])
    #print(la*(len(c)-ra))
    ans+=la*(len(c)-ra)
#print(ans)
#la=bisect.bisect_left(a, 8)
#ra=bisect.bisect_right(a, 8)
#print(la,len(a)-ra)

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

import sys
n = int(sys.stdin.readline())
s_list = [sorted(list(sys.stdin.readline().rstrip())) for x in range(n)]
count = 0
for x in range(len(s_list)):
    for y in range(x+1, len(s_list)):
        if s_list[x] == s_list[y]:
            count += 1
print(count)


### FIXED CODE ###

import sys
from collections import Counter
import math

N = int(sys.stdin.readline())
s_list = ["".join(sorted(list(sys.stdin.readline().rstrip()))) for x in range(N)]
s_list = Counter(s_list)
count = 0
for i in s_list.values():
    if i == 1:
        continue
    count += (math.factorial(i) // math.factorial(i - 2)) // math.factorial(2)
print(count)