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

import math

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 += math.gcd(math.gcd(a,b),c)

print(ans)


### FIXED CODE ###

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a,b)
    for c in range(1,k+1):
      ans += math.gcd(c,tmp)

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

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

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
for i in range(W):
    if S[0][i] == ".":
        U[0][i] = 1
    if S[H-1][i] == ".":
        D[H-1][i] = 1

for i in range(H):
    if S[i][0] == ".":
        L[i][0] = 1
    if S[i][W-1] == ".":
        R[i][W-1] = 1
     
for i in range(1,H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        U[i][j] = U[i-1][j] + 1
for i in range(H-1)[::-1]:
    for j in range(W):
        if S[i][j] == "#":
            continue
        D[i][j] = D[i+1][j] + 1
for i in range(H):
    for j in range(1,W):
        if S[i][j] == "#":
            continue
        L[i][j] = L[i][j-1] + 1
for i in range(H):
    for j in range(W-1)[::-1]:
        if S[i][j] == "#":
            continue
        R[i][j] = R[i][j+1] + 1
        
ans = 0

for i in range(H):
    for j in range(W):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
print(ans)
        

### FIXED CODE ###

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

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
for i in range(W):
    if S[0][i] == ".":
        U[0][i] = 1
    if S[H-1][i] == ".":
        D[H-1][i] = 1

for i in range(H):
    if S[i][0] == ".":
        L[i][0] = 1
    if S[i][W-1] == ".":
        R[i][W-1] = 1
     
for i in range(1,H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        U[i][j] = U[i-1][j] + 1
for i in range(H-1)[::-1]:
    for j in range(W):
        if S[i][j] == "#":
            continue
        D[i][j] = D[i+1][j] + 1
for i in range(H):
    for j in range(1,W):
        if S[i][j] == "#":
            continue
        L[i][j] = L[i][j-1] + 1
for i in range(H):
    for j in range(W-1)[::-1]:
        if S[i][j] == "#":
            continue
        R[i][j] = R[i][j+1] + 1
        
ans = 0

for i in range(H):
    for j in range(W):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
print(ans)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
history = []
now = 0
cnt = 0
while(True):
    if now in history:
        cnt = -1
        break
    else:
        cnt += 1
        history.append(now)
        now = a[now]-1
        if now == 1:
            break
print(cnt)

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
history = set()
now = 0
cnt = 0
while(True):
    if now in history:
        cnt = -1
        break
    else:
        cnt += 1
        history.add(now)
        now = a[now]-1
        if now == 1:
            break
print(cnt)
### BUGGY CODE ###

S=input()

comb=[]
for i in range(len(S)-3):
    for j in range(i+3,len(S)):
        if int(S[i:j+1])%2019==0:
            comb.append((i+1,j+1))

print(len(comb))


### FIXED CODE ###

S=input()
S=list(reversed(S))

m=2019
cnt=[0 for i in range(m)]

len_S=len(S)
x=1
tot=0
ans=0

for i in range(len(S)):
    cnt[tot]+=1
    tot+=(ord(S[i])-ord('0'))*x
    tot %= m
    ans+=cnt[tot]
    x=x*10%m

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

def main():
    import sys
    input=sys.stdin.readline
    import numpy as np

    n,k=map(int,input().split())
    A=np.array(input().split(),np.int64)
    F=np.array(input().split(),np.int64)
    A.sort()
    F.sort()
    F=F[::-1]

    def ok(x): #チームの成績をxとするような修行の仕方が存在するか
        B=A-(x//F)
        return sum(B[B>0])<=k
    
    l=-1
    r=10**18
    while r-l>1:
        mid=(r+l)//2
        if ok(mid):
            r=mid
        else:
            l=mid
    print(r)   

if __name__=='__main__':
    main()

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
F = np.array(input().split(), dtype=np.int64)
A = np.sort(A)
F = np.sort(F)[::-1]


def C(x):
    train = np.maximum(0, A - x // F).sum()
    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)
### BUGGY CODE ###

def gcd_seq(seq):
    from fractions import gcd
    size = len(seq)
    if size == 1:
        return seq[0]
    if size == 2:
        return gcd(seq[0], seq[1])
    ans = gcd(seq[0], seq[1])
    for i in range(2, size):
        ans = gcd(seq[i], ans)
    return ans


N = int(input())
A = [int(i) for i in input().split()]

ANS = gcd_seq(A)  # no change
for i in range(N):
    a = A[:]
    a.pop(i)
    ANS = max((gcd_seq(a), ANS))
print(ANS)



### FIXED CODE ###

def gcd(a, b):
    bigger = max(a, b)
    smaller = min(a, b)
    while smaller != 0:
        bigger, smaller = smaller, bigger % smaller
    return bigger


N = int(input())
A = list(map(int, input().split()))
gcd_l = [A[0]] + [0] * (N - 1)
for i in range(1, N):
    gcd_l[i] = gcd(gcd_l[i - 1], A[i])
del gcd_l[-1]

gcd_r = [0] * (N - 1) + [A[-1]]
for i in range(N - 1, 0, -1):
    gcd_r[i - 1] = gcd(gcd_r[i], A[i - 1])
del gcd_r[0]

gcds = [gcd_l.pop(), gcd_r.pop(0)]
for l, r in zip(gcd_l, gcd_r):
    gcds.append(gcd(l, r))
print(max(gcds))
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
MOD = 998244353

dp = [[0 for _ in range(D+1)] for _ in range(C+1)]
dp[A][B] = 1
#dp[i][j] ヨコi番目でそこまでの最大の高さがj

for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A:
      dp[i][j] += dp[i-1][j]*j
    if j > B:
      dp[i][j] += dp[i][j-1]*i
    if i > A and j > B:
      dp[i][j] -= dp[i-1][j-1]*(i-1)*(j-1)
    dp[i][j] %= MOD

ans = dp[C][D]
print(ans)
      

### FIXED CODE ###

A,B,C,D = map(int,input().split())
MOD = 998244353

dp = [[0 for _ in range(D+1)] for _ in range(C+1)]
dp[A][B] = 1
#dp[i][j] ヨコi番目でそこまでの最大の高さがj

for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A:
      dp[i][j] += dp[i-1][j]*j
    if j > B:
      dp[i][j] += dp[i][j-1]*i
    if i > A and j > B:
      dp[i][j] -= dp[i-1][j-1]*(i-1)*(j-1)
    dp[i][j] %= MOD

ans = dp[C][D]
print(ans)
### BUGGY CODE ###

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

b=[-1]*N
b[N-1]=a[N-1]
for i in range(N-1)[::-1]: #N=4なら 2,1,0
    sum_count = N // (i+1)
    if sum_count==1:
        b[i]=a[i]
    else:
        sum1=0
        for j in range(sum_count-1):
            sum1 = sum1 + b[(i+1)*(j+2)-1]
        sum1 = sum1 % 2
        b[i]=(a[i]+ sum1)%2

print(sum(b))
f=0
for i in range(N):
    if b[i]==1 and f==0:
        f=1
        out=str(i+1)
    elif b[i]==1:
        out = out + " " + str(i+1)
if f==1:
    print(out)

### FIXED CODE ###

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

b=[-1]*N
b[N-1]=a[N-1]
for i in range(N-1)[::-1]: #N=4なら 2,1,0
    sum_count = N // (i+1)
    if sum_count==1:
        b[i]=a[i]
    else:
        sum1=0
        for j in range(sum_count-1):
            sum1 = sum1 + b[(i+1)*(j+2)-1]
        sum1 = sum1 % 2
        b[i]=(a[i]+ sum1)%2

print(sum(b))
for i in range(N):
    if b[i]==1:
        print(i+1,end=" ")
### BUGGY CODE ###

n = int(input())
s = str(input())
s_shift = s
ans = 0

for i in range(n):
    s_shift = '_' + s_shift
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(n):
        if s[j] == s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

print(ans)

### FIXED CODE ###

from collections import deque
import copy

n = int(input())
s = str(input())

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(i+1,n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

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

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
for i in range(n-1):
  #b = 0
  b = sum(S[i+1:n]) % divisor
  #for j in range(i+1,n):
  #  b += S[j]
  #  if b >= divisor:
  #    b = b % divisor
  a = S[i]
  #tot += multmod(a,b,divisor)
  tot += a*b % divisor
  #if tot >= divisor:
  #  tot = tot % divisor

tot = tot % divisor
print(tot)

### FIXED CODE ###

def multmod(a,b,m):
  ans = 0
  a = a % m
  
  while b:
    if (b & 1): # odd
      ans = (ans + a) % m
    
    a = (2 * a) % m
    b >>= 1 # b = b / 2
    
  return ans

n = int(input())
S = [int(a) for a in input().split()]
divisor = 10**9 + 7
tot = 0
a,b = 0,0
arr_sum = sum(S) #% divisor
arr_ssq = arr_sum*arr_sum #% divisor
isq_sum = 0
for i in range(n):
  isq_sum += S[i]*S[i] #% divisor
  
#isq_sum = isq_sum % divisor
tot = (arr_ssq - isq_sum)//2 % divisor

print(tot)
### BUGGY CODE ###

n,W = map(int,input().split())
w = [0]*n ; v = [0]*n
for i in range(n) :
    w[i],v[i] = map(int,input().split())
max_v = max(v)


# dp[i][j] = i番目までの荷物をいくつか選んで価値をjぴったりにしたときの重さの最小値
dp = [[10**18]*(n*max_v+1) for i in range(n)]
# 価値を0ぴったりにする重さの最小値は0
for i in range(n) :
    dp[i][0] = 0

for i in range(n) :
    for j in range(n*max_v+1) :
        if j-v[i] >= 0 : # i番目の荷物を選んで価値をjぴったりにできる場合
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]]+w[i])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

for j in range(n*max_v,-1,-1) :
    if dp[n-1][j] <= W :
        print(j)
        break

### FIXED CODE ###

n,W = map(int,input().split())
w = [0]*n ; v = [0]*n
for i in range(n) :
    w[i],v[i] = map(int,input().split())
max_v = max(v)


# dp[i][j] = i番目までの荷物をいくつか選んで価値をjぴったりにしたときの重さの最小値
dp = [[10**18]*(n*max_v+1) for i in range(n)]
# 価値を0ぴったりにする重さの最小値は0
for i in range(n) :
    dp[i][0] = 0

for i in range(n) :
    for j in range(n*max_v+1) :
        if j-v[i] >= 0 : # i番目の荷物を選んで価値をjぴったりにできる場合
            dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]]+w[i])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

for j in range(n*max_v,-1,-1) :
    if dp[n-1][j] <= W :
        print(j)
        break
### BUGGY CODE ###

n = int( raw_input() )
eles = []
for i in range( n ):
	op = raw_input( ).split( " " )
	if "insert" == op[0]:
		eles.insert( 0, op[1] )
	elif "delete" == op[0]:
		if op[1] in eles:
			eles.remove( op[1] )
	elif "deleteFirst" == op[0] :
		eles.pop( 0 )
	elif "deleteLast" == op[0]:
		eles.pop( )

print( " ".join( eles ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


print( " ".join( que ) )
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for x in range(N // R + 1):
	for y in range(N // G + 1):
		if (N - R * x - G * y) % B == 0 and 0 <= (N - R * x - G * y) // B <= N // B:
			ans += 1
print(ans)


### FIXED CODE ###

R ,G, B, N = map(int, input().split())
ans = 0
for r in range(N // R + 1):
	for g in range(N // G + 1):
		if (N - R * r - G * g) % B == 0 and 0 <= (N - R * r - G * g) // B <= N // B:
			ans += 1
print(ans)
### BUGGY CODE ###

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


num_ac = [0] * n

for i in range(n):
    num_ac[i] = s[:i+1].count("AC")

ans = [0] * q
for i in range(q):
    l,r = map(int, input().split())
    ans[i] = num_ac[r-1] - num_ac[l-1]

for a in ans:
    print(a)



### FIXED CODE ###

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


num_ac = [0] * n
num_ac[0] = 0
if s[0] == "A" and s[1] == "C":
    num_ac[1] = 1


for i in range(2,n):
    if s[i-1] == "A" and s[i] == "C":
        num_ac[i] = num_ac[i-1] + 1
    else:
        num_ac[i] = num_ac[i-1]

ans = [0] * q
for i in range(q):
    l,r = map(int, input().split())
    ans[i] = num_ac[r-1] - num_ac[l-1]

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

n,x,y=map(int,input().split())
ans=[0 for i in range(n)]
for start in range(n):
  gone=[0 for i in range(n)]
  gone[start]=1
  now ={start}
  for i in range(1,n):
    go=set()
    for s in now:
      if s!=0 and gone[s-1]==0:
        go.add(s-1)
        gone[s-1]=1
        ans[i]+=1
      if s!=n-1 and gone[s+1]==0:
        go.add(s+1)
        gone[s+1]=1
        ans[i]+=1
      if s==x-1 and gone[y-1]==0:
        go.add(y-1)
        gone[y-1]=1
        ans[i]+=1
      if s==y-1 and gone[x-1]==0:
        go.add(x-1)
        gone[x-1]=1
        ans[i]+=1
    now=go
for i in range(1,n):
  print(ans[i]//2)


### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0 for i in range(n)]
for start in range(n):
  gone=[0 for i in range(n)]
  gone[start]=1
  now ={start}
  for i in range(1,n):
    go=set()
    for s in now:
      if s!=0 and gone[s-1]==0:
        go.add(s-1)
        gone[s-1]=1
        ans[i]+=1
      if s!=n-1 and gone[s+1]==0:
        go.add(s+1)
        gone[s+1]=1
        ans[i]+=1
      if s==x-1 and gone[y-1]==0:
        go.add(y-1)
        gone[y-1]=1
        ans[i]+=1
      if s==y-1 and gone[x-1]==0:
        go.add(x-1)
        gone[x-1]=1
        ans[i]+=1
    now=go
for i in range(1,n):
  print(ans[i]//2)
### BUGGY CODE ###

def main():
  
    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = set(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

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

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
cost = [[-1]*n for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    cost[a][b]=c
    cost[b][a]=c

q, k = map(int, input().split())
xy = [tuple(map(int,input().split())) for i in range(q)]

dist = [-1]*n

def dfs(v=0,parent=-1):

    if dist[v]==-1:
        dist[v] = dist[parent] + cost[v][parent]
    for i,d in enumerate(cost[v]):
        if d!=-1 and dist[i]==-1:
            dfs(i,v)

dist[k-1] =0
dfs(k-1)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

print(*ans,sep='\n')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

q, k = map(int, input().split())
xy = [tuple(map(int,input().split())) for i in range(q)]

dist = [-1]*n

def dfs(v=0,parent=-1,d=0):
    for next_v,dd in es[v]:
        if dist[next_v] == -1:
            dist[next_v] = d + dd
            dfs(next_v,v,dist[next_v])

dist[k-1] =0
dfs(k-1,-1,0)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

print(*ans,sep='\n')
### BUGGY CODE ###

#from math import gcd
from fractions import gcd
#from functools import reduce


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	#ans = reduce(lcm, A)
	
	a = 1
	for i in A:
		a = lcm(a, i)

	#print(a, ans)
	B = [a//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

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


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

l,r = map(int,input().split())
r = min(r,l+4038)
mini = 2018
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans = ( i*j )% 2019
    mini = min(ans,mini)
print(mini)


### FIXED CODE ###

l,r = map(int,input().split())
if (r-l)>=2019:
  print(0)
else:
  mini = 2018
  for i in range(l,r+1):
    for j in range(i+1,r+1):
      ans = ( i*j )% 2019
      mini = min(ans,mini)
  print(mini)
### BUGGY CODE ###

# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2]: 1; left, 2; lower, 3; upper, 4; right
    if y1 < y2:
        p1 = (x1, y1, 2)
        p2 = (x2, y2, 3)
    elif y1 > y2:
        p1 = (x1, y1, 3)
        p2 = (x2, y2, 2)
    elif x1 < x2:
        p1 = (x1, y1, 1)
        p2 = (x2, y2, 4)
    else:
        p1 = (x1, y1, 4)
        p2 = (x2, y2, 1)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0], p[2]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        position = p[2]
        if position == 3:
            T.remove(p[0])
            if flag:
                cnt += 1
        elif position == 2:
            bisect.insort(T, p[0])
        elif position == 4:
            cnt += bisect.bisect(T, p[0]) - left_end
            flag = False
        else:
            left_end = bisect.bisect_left(T, p[0])
            flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

### FIXED CODE ###

# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))
        h_num += 1

# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n

    def switch(self, i, d):
        while  i <= self.num:
            self.data[i] += d
            i += i & -i

    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)

# Sweep
import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e: i for i, e in enumerate(vs_x)}
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        BIT.switch(d_vs_x[p[2]], 1)
    elif e == u:
        BIT.switch(d_vs_x[p[2]], -1)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += BIT.seg_sum(l_x, r_x)
        h_num -= 1
    if h_num == 0:
        break

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

n=int(input())
l=list(map(int,input().split()))
d=dict()

for i in range(len(l)):
  d.setdefault(l[i],0)
  d[l[i]] += 1

for i in range(len(l)):
    d[l[i]] -= 1
    result=0
    for key,value in d.items():
        num=(value*(value-1))/2
        result += num
    d[l[i]] += 1
    print(int(result))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
d=dict()

for i in range(len(l)):
  d.setdefault(l[i],0)
  d[l[i]] += 1

result=0

for key,value in d.items():
    num=(value*(value-1))/2
    result += num

for i in range(len(l)):
    r1=int((d[l[i]]*(d[l[i]]-1))/2)
    r2=int(((d[l[i]]-1)*(d[l[i]]-2))/2)
    output=int(result-r1+r2)
    print(output)
### BUGGY CODE ###

from collections import Counter as ct

N = int(input())
s = []
k = []
a = 0

for i in range(N):
    str = input()
    s.append(ct(str))

for i in range(N - 1):
    for j in range(i + 1, N):
        if s[i] == s[j]:
            a += 1

print(a)


### FIXED CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

for s in S:
    s.sort()

S.sort()

cnt = 1
ans = 0
tmp = []

for s in S:
    if s == tmp:
        cnt += 1
    else:
        tmp = s
        ans += cnt * (cnt - 1) // 2
        cnt = 1

ans += cnt * (cnt - 1) // 2

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

# -*- coding: utf-8 -*-
"""
Created on Fri Jun 12 21:52:40 2020

@author: naoki
"""

N = int(input()) # 並んでいる人数N

S = input() # 向いている方向

direction = [0 for i in range(N)] 

for i in range(N):
    direction[i] = S[i] # 向いている方向を開裂で定義しなおす
    
count = [0 for i in range(N)] # 向きを変える回数

for i in range(N):
    for k in range(N):
        if k<i and direction[k] == "W": #リーダーよりも西側にいる場合は東に向かせる
            count[i] += 1
        elif i<k and direction[k] == "E": # リーダーよりも東側にいる場合は西に向かせる
            count[i] += 1
count.sort() # 値が小さい順番に並び替える
print(count[0])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Jun 12 21:52:40 2020

@author: naoki
"""

N = int(input()) # 並んでいる人数N

S = input() # 向いている方向
    
change = [0 for i in range(N)] # 向きを変えた回数を格納
change[0] = S.count("E",1,N)
for i in range(1,N):
        if S[i-1] == "W" and S[i] == "E":
            change[i] = change[i-1]
        elif S[i-1] == "W" and S[i] != "E": 
            change[i] = change[i-1] + 1
        elif S[i-1] != "W" and S[i] == "E":
            change[i] = change[i-1] - 1
        else:
            change[i] = change[i-1]
change.sort()
print(change[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
A = sorted((map(int,input().split())), reverse=True)
F = sorted(map(int,input().split()))

def judge(k):
    cnt = 0
    for a, f in zip(A, F):
        x = k//f
        d = a - x if a > x else 0
        cnt += d
    if cnt <= K:
        return True
    else:
        return False

def biserch(ok,ng,judge):
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        if judge(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = biserch(10**12, -1, judge)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
A = sorted((map(int,input().split())), reverse=True)
F = sorted(map(int,input().split()))

def judge(k):
    cnt = 0
    for a, f in zip(A, F):
        x = k//f
        d = a - x if a > x else 0
        cnt += d
    if cnt <= K:
        return True
    else:
        return False

def biserch(ok,ng,judge):
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        if judge(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = biserch(10**12, -1, judge)
print(ans)