Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

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

l = [[] for _ in range(M)]
for j in range(M):
    b,c = [int(i) for i in input().split()]
    l[j] = [c,b]

l.sort(reverse=True)
A.sort()
ans = 0

for i,j in l:
    for k in range(N):
        if i <= A[k]:
            break
    k = min(k,j)
    ans += k*i
    A = A[k:]
if A:
    print(ans+sum(A))
else:
    print(ans)


### FIXED CODE ###

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
bc = [tuple(int(i) for i in input().split()) for _ in range(M)]

A.sort()
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = 0
for i in range(N):
    if index >= M or A[i] >= bc[index][1]:
        break
    A[i] = bc[index][1]
    count += 1
    if bc[index][0] <= count:
        index += 1
        count = 0

print(sum(A))
N = int(input())
A = list(map(int,input().split()))
if A[0] == 0 or A[N-1] == 0:
  A_tmp = A[0]
  A_ = A[1:N]
  A_.append(A_tmp)
  A = A_
  flag = 1
else:
  flag = 0
if A[0]<A[N-1]:
  start = A[0]
else:
  start = A[N-1]
for i in range(2*start-2,1,-2):
  ans = [i]
  A_tmp = A[:]
  A_tmp[0] -= ans[0]//2
  A_tmp[N-1] -= ans[0]//2 
  for j in range(1,N):
    if A_tmp[j-1]<A_tmp[j]:
      ans.append(A_tmp[j-1]*2)
      A_tmp[j] -= ans[j]//2
      A_tmp[j-1] -= ans[j]//2
    else:
      ans.append(A_tmp[j]*2)
      A_tmp[j] -= ans[j]//2
      A_tmp[j-1] -= ans[j]//2
  if sum(A_tmp)==0:
    break
if flag == 1:
  tmp = [0]*N
  tmp[1:] = ans[:N-1]
  tmp[0] = ans[N-1]
  ans = tmp
ans = map(str,ans)
print(' '.join(ans))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = sum(A)//2
S = 2*(S - sum(A[1::2]))
ans = [S]
for i in range(1,N):
  ans.append(2*A[i-1]-ans[i-1])
print(' '.join(map(str,ans)))
a=input()
b=input().split()

l=[int(i) for i in b]

cnt=[0 for i in range(a)]

for i in range(a):
    while l[i]%2==0:
        cnt[i]+=1
        l[i]=l[i]/2
        if l[i]%2==1:
            break

print(min(cnt))

### FIXED CODE ###

a=int(input())
b=input().split()
 
l=[int(i) for i in b]
 
cnt=[0 for i in range(a)]
 
for i in range(a):
    while l[i]%2==0:
        cnt[i]+=1
        l[i]=l[i]/2
        if l[i]%2==1:
            break
 
print(min(cnt))
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
for _ in range(Q):
    B,C = map(int, input().split())
A.sort()
ans = 0
for a in range(Q) :
    x=C if A=B else 0
    ans = sum(A)
print(ans)
        

### FIXED CODE ###

a = input()
if a.isupper()== True :
    print('A')
else :
    print('a')
import sys
sys.setrecursionlimit(2147483647)

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

#n,m<=10**5

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(m+1) #初期化

lastcheck=set([])
klkl=[]
for _ in range(n):
    kl=list(map(int,input().split()))[1:]
    if len(kl)==1:
        lastcheck.add(kl[0])
    else:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(item-1)    

flag=0
for kl in klkl:
    for item in kl:
        item-=1
        if item not in uf_list:
            flag=1
if flag==1:
    print("NO")
else:
    print("YES")
    














### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

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

#n,m<=10**5

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(m+1) #初期化

lastcheck=set([])
klkl=[]
for _ in range(n):
    kl=list(map(int,input().split()))[1:]
    if len(kl)>1:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(klkl[0][0]-1)
#print(uf_list)
flag=0
for kl in klkl:
    for item in kl:
        item-=1
        if item not in uf_list:
            flag=1
        else:
            break
if flag==1:
    print("NO")
else:
    print("YES")
import sys
n,m = map(int,input().split())
sc = [list(map(int,input().split())) for i in range(m)]

l = [0 for i in range(n)]
set_sc = [[] for i in range(n)]

for i in range(m):
    set_sc[sc[i][0]-1].append(sc[i][1])

for i in range(m):
    if len(set(set_sc[i])) > 1:
        print(-1)
        sys.exit()

if set_sc[0][0] == 0:
    print(-1)
    sys.exit()

for i in range(n):
    if len(set_sc[i]) == 0:
        continue
    l[i] = set_sc[i][0]

l = list(map(str,l))
print(''.join(l))

### FIXED CODE ###

import sys
n,m = map(int,input().split())
sc = [list(map(int,input().split())) for i in range(m)]

for i in range(10**n):
    s = str(i)
    if len(s) != n:
        continue
    c = 0
    for i in range(m):
        if n >= 2:
            if sc[i] == [1,0]:
                print(-1)
                sys.exit()
            
        if s[sc[i][0]-1] == str(sc[i][1]):
            c += 1
    
    if c == m:
        print(s)
        sys.exit()

print(-1)
N, K = map(int, input().split())
num = ["0","1","2","3","4","5","6","7","8","9"]
dis = input().split()
can_use = sorted(list(set(num)-set(dis)))

sN = str(N)
L = len(sN)
ans = ""

for i in range(1,L):
    if sN[i] in can_use:
        ans += sN[i]
    else:
        ans += min(can_use)

if sN[0] in can_use:
    ans += sN[0]
else:
    if can_use[0] == "0":
        ans = can_use[1] + ans
    else:
        ans = can_use[0] + ans

if int(ans) < N:
    if can_use[0] != "0":
        ans = ans + can_use[1]
    else:
        ans = ans + can_use[0]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
dislike = list(map(str, input().split()))
num = ["0","1","2","3","4","5","6","7","8","9"]
can_use = set(num) - set(dislike)

while not set(list(str(N))) <= can_use:
    N += 1

print(N)
n, m = map(int, input().split())
rootList = [-1 for i in range(n)]
 
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        rootList[x] = rootList[y] = min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) else "no")

### FIXED CODE ###

n, m = map(int, input().split())
rootList = [-1 for i in range(n)]
 
def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    if x != y:
        rootList[x] = rootList[y] = min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) else "no")
import math
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0: 
        return 1
    elif y == 1: 
        return x % mod
    elif y % 2 == 0 : 
        return power(x, y//2)**2 % mod
    else: 
        return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))
X,Y = map(int,input().split())
s = (2*Y-X)//3
t = (2*X-Y)//3
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
    print(0)
else:
    a = math.factorial(s+t)%mod
    
    b = math.factorial(s)
    c = math.factorial(t)
    ans = div(div(a,b),c)
    print(ans)

### FIXED CODE ###

def combination(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % p
 
    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % p
 
    return (numerator * pow(denominator, p-2, p)) % p
 
 
X, Y = map(int, input().split())
 
a = (2*Y-X) / 3
b = (2*X-Y) / 3
 
if a >= 0 and b >= 0 and a == int(a) and b == int(b):
    a = int(a)
    b = int(b)
 
    print(combination(a+b, a, 10**9+7))
else:
    print(0)
N = int(input())
A = list(map(int, input().split()))

S = sorted(A)
MAXS = max(A)

for i in range(N):
    if A[i] == MAXS:
        print(S[-2])
    else:
        print(S[-1])


### FIXED CODE ###

# N = int(input())
# A = list(map(int, input().split()))
# 
# S = sorted(A)
# MAXS = max(A)
# 
# for i in range(N):
#     if A[i] == MAXS:
#         print(S[-2])
#     else:
#         print(S[-1])
# 


n = int(input())
a = list()
for i in range(n):
    a.append(int(input()))
c = a.index(max(a))
m = max(a)
a.sort()
d = a[-2]
for i in range(n):
    if i == c:
        print(d)
    else:
        print(m)
N, C = map(int, input().split())
X, V = [], []
for i in range(N):
    xi, vi = map(int, input().split())
    X.append(xi)
    V.append(vi)

r_cal = [0]
l_cal = [0]
for i in range(N):
    r_cal.append(r_cal[-1] + V[i])
    l_cal.append(l_cal[-1] + V[N-i-1])

# 折り返さないパターン and 折り返してどこまでいくのか
r_straight = r_cal.copy()
l_straight = l_cal.copy()

for i in range(1, N+1):
    r_straight[i] -= X[i-1]
    l_straight[i] -= (C - X[N-i])

# 折り返すパターン
for i in range(1, N+1):
    r_cal[i] -= 2*X[i-1]
    l_cal[i] -= 2*(C - X[N-i])

# 折り返した後どこまで行くのが最適か
r_max = [0]
l_max = [0]
for i in range(1, N+1):
    r_max.append(max(r_max[-1], r_straight[i]))
    l_max.append(max(l_max[-1], l_straight[i]))

ans = max(r_max[-1], l_max[-1])
for i in range(N):
    ans = max(ans, r_cal[i] + l_max[N-i])
    ans = max(ans, l_cal[N-i] + r_max[i])
print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
X, V = [], []
for i in range(N):
    xi, vi = map(int, input().split())
    X.append(xi)
    V.append(vi)

r_cal = [0]
l_cal = [0]
for i in range(N):
    r_cal.append(r_cal[-1] + V[i])
    l_cal.append(l_cal[-1] + V[N-i-1])

# 折り返さないパターン and 折り返してどこまでいくのか
r_straight = r_cal.copy()
l_straight = l_cal.copy()

for i in range(1, N+1):
    r_straight[i] -= X[i-1]
    l_straight[i] -= (C - X[N-i])

# 折り返すパターン
for i in range(1, N+1):
    r_cal[i] -= 2*X[i-1]
    l_cal[i] -= 2*(C - X[N-i])

# 折り返した後どこまで行くのが最適か
r_max = [0]
l_max = [0]
for i in range(1, N+1):
    r_max.append(max(r_max[-1], r_straight[i]))
    l_max.append(max(l_max[-1], l_straight[i]))

ans = max(r_max[-1], l_max[-1])
for i in range(N):
    ans = max(ans, r_cal[i] + l_max[N-i])
    ans = max(ans, l_cal[N-i] + r_max[i])
    
print(ans)
import math

def myfactorial(n):
  return math.factorial(n) % 1000000007

def combinations_count(n, r):
    return (myfactorial(n) // ((myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  print(combinations_count(k-1, i-1) * combinations_count(i+1+(n-k)-(i-1)-1, (n-k)-(i-1)) % 1000000007) 

### FIXED CODE ###

import math

def myfactorial(n):
  return math.factorial(n)

def combinations_count(n, r):
  return (myfactorial(n) // (myfactorial(n - r) * myfactorial(r))) % 1000000007

n, k = map(int, input().split())
for i in range(1, k+1):
  if n-k+1 < i:
    print(0)
  else:
    print(combinations_count(k-1, i-1) * combinations_count(n-k+1, i) % 1000000007)
def getdata_input():
    while True:
        yield input()

def callFunc2(it):
    A0,B0,K=map(int, next(it).split())
    A=[0]
    B=[0]
    n=K//2

    A.append(min(n,A0))
    B.append(min(n,B0))

    n=K-(sum(A)+sum(B))
    
    if n>0:
        t=A0-sum(A)
        A.append(min(n, t))
        n=n-t
    if n > 0:
        t=B0-sum(B)
        B.append(min(n,t))
    return(f'{A0-sum(A)} {B0-sum(B)}')
  
it=getdata_input()
print(callFunc2(it))

### FIXED CODE ###

def getdata_input():
    while True:
        yield input()
def callFunc2(it):
    A0,B0,K=map(int, next(it).split())
    A=[0]
    B=[0]
    
    t=min(K,A0)
    A.append(t)
    t=min(K-t,B0)
    B.append(min(t,B0))
    return(" ".join([str(A0-sum(A)), str(B0-sum(B))]))
  
it=getdata_input()
print(callFunc2(it))
def insertionSort(A,n,g):
    for i in range(g,n,1):
        v = int(A[i])
        j = i - g
        while j >= 0 and int(A[j]) > v:
            global cnt
            A[j + g] = A[j]
            j = j - g
            cnt = cnt + 1
        A[j+g] = str(v)
            
def shellSort(A,n):
    global cnt
    global G
    G = []
    cnt = 0
    h = 1
    while h <= n:
        G.append(h)
        h = 3*h + 1
        if(len(G)>100):
            break
    m = len(G)
    print(m)
    G.reverse()
    print(' '.join(map(str, G)))
    for i in range(0,m,1):
        insertionSort(A,n,G[i])
    print(cnt)
        

n = int(input())
#改行で標準入力を受け付ける場合
A = []
for i in range(n):
    A.append(input())
shellSort(A,n)
print('\n'.join(A))


### FIXED CODE ###

import sys


def print_A(A):
    for i in range(len(A)):
        sys.stdout.write(str(A[i]))
        if i!= len(A) -1:
            sys.stdout.write(' ')
    print()


def insertionSort(A,n,g):
    cnt = 0
    for i in range(g,n):
        v = A[i]
        j = i - g
        while (j>=0) and (A[j] > v):
            A[j + g] = A[j]
            j -= g
            cnt +=1
        A[j + g] = v
    return cnt

def shellSort(A,n,G):
    cnt = 0
    for i in range(len(G)):
        cnt += insertionSort(A,n,G[i])
    return cnt
        

def get_gap(n):
    G = []
    h = 1
    cnt = 1
    while h <= n:
        G.append(h)
        h = 3*h + 1
        cnt +=1
    if len(G) == 0: G.append(1)
    return list(reversed(G))


n = int(input())
A = [0] * n
for i in range(n):
    A[i] = int(input())
    
G = get_gap(n)
m = len(G)
cnt = shellSort(A,n,G)

print(m)
print_A(G)
print(cnt)
for i in range(n):
    print(A[i])
def Recording():
    n, c = map(int, input().split())
    num = 30#2*10**5+1 

    # チャンネルごとにimos配列
    imos = [[0]*num for _ in range(c)]
    
    # imos
    for _ in range(n):
        s, t, c0 = map(int, input().split())
        if imos[c0-1][s*2] < 0 and imos[c0-1][t*2-1] > 0:
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] = 0
        elif imos[c0-1][s*2] < 0:            
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] += 1
        elif imos[c0-1][t*2-1] > 0:    
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2-1] = 0
        else:
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2] -= 1
    ans = [0 for _ in range(num)]
    for i in range(c):
        for j in range(1, num):
            imos[i][j] += imos[i][j-1]
            ans[j] += imos[i][j]
    print(max(ans))
    
if __name__ == '__main__':
    Recording()
    


### FIXED CODE ###

def Recording():
    n, c = map(int, input().split())
    num = 2*10**5+1 

    # チャンネルごとにimos配列
    imos = [[0]*num for _ in range(c)]
    
    # imos
    for _ in range(n):
        s, t, c0 = map(int, input().split())
        if imos[c0-1][s*2] < 0 and imos[c0-1][t*2-1] > 0:
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] = 0
        elif imos[c0-1][s*2] < 0:            
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2] -= 1
        elif imos[c0-1][t*2-1] > 0:    
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2-1] = 0
        else:
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2] -= 1
    ans = [0 for _ in range(num)]
    for i in range(c):
        for j in range(1, num):
            imos[i][j] += imos[i][j-1]
            ans[j] += imos[i][j]
    print(max(ans))
    
if __name__ == '__main__':
    Recording()
import sys
def solve():
  for x in sys.stdin:
  a,b = map(int,raw_input().split())
  print a*b,2*a+2*b
  
if __name__ == "__main__":
  solve()

### FIXED CODE ###

input = raw_input().split()
a = int(input[0])
b = int(input[1])
print "%d %d" % (a * b , 2 * (a + b))
def main():
  n,m = map(int,input().split())
  s = list(map(int,input.split()))
  cs = s
  for i in range(m):
    a,b = map(int,input().split())
    a-=1,b-=1
    if(s[a] < s[b]):
      cs[a]=-1
    else if(s[a] == s[b]):
      cs[a]=-1
      cs[b]=-1
    else:
      cs[b]=-1
  print(cs.count(-1))
      
if __name__ == '__main__':
  main()

### FIXED CODE ###

N, M =map(int, input().split())
H_tree = [0] + [int(n) for n in input().split()]
GOOD_Tree = [0] + [1 for n in range(N)]
 
for i in range(M):
  A, B = map(int, input().split())
  if H_tree[A]<=H_tree[B]:GOOD_Tree[A] = 0
  if H_tree[A]>=H_tree[B]:GOOD_Tree[B] = 0
print(sum(GOOD_Tree))
W = 101

def solve(N, xyh):
    for yy in range(W):
        for xx in range(W):
            H = set()
            Z = 1e9
            for x, y, h in xyh:
                d = abs(xx - x) + abs(yy - y)
                if h > 0:
                    H.add(d + h)
                else:
                    Z = min(Z, d)
            if len(H) == 1:
                h = H.pop()
                if 0 < h <= Z:
                    return (xx, yy, h)

N = int(input())
xyh = [tuple(map(int, input().split())) for i in range(N)]
print(*solve(N, xyh))

### FIXED CODE ###

W = 101

def solve(xyh):
    for bx, by, bh in xyh:
        if bh > 0:
            break
    for yy in range(W):
        for xx in range(W):
            H = bh + abs(bx - xx) + abs(by - yy)
            for x, y, h in xyh:
                if max(H - abs(xx - x) - abs(yy - y), 0) != h:
                    break
            else:
                return (xx, yy, H)

N = int(input())
xyh = [tuple(map(int, input().split())) for i in range(N)]
print(*solve(xyh))
N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
value = dict()
for px in PX:
    value.setdefault(px[0],0)
    value[px[0]] += px[1]
tree = dict()
for ab in AB:
    tree.setdefault(ab[0],[])
    tree[ab[0]].append(ab[1])
from collections import deque
Q = deque([1])
while Q:
    q = Q.pop()
    tree.setdefault(q,[])
    for c in tree[q]:
        value.setdefault(c,0)
        value.setdefault(q,0)
        value[c] += value[q]
        Q.append(c)
ans = []
for n in range(N):
    ans.append(value[n+1])
print(*ans)

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])
N, W = map(int, input().split())

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    for j in DP:
        if j+wi <= W:
            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)
    DP = DP_dst
print(max((DP[x] for x in DP)))

### FIXED CODE ###

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

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])
N=int(input())
A=map(int(),input().split()) 
ans=0
for a in A:
  ans+=a
print(ans)

### FIXED CODE ###

N=int(input())
A=map(int,input().split()) 
ans=0
for a in A:
  ans += 1/a
print(1/ans)
N,D = map(int,input().split())
#N,Dを入力
k = []
#座標のリストを作成
a = 0
#一時的に代入する値を作成
for i in range(N):
  k.append(map(int,input().split())
for i in range(N):
  for j in range(D):
#D回をN回繰り返す
    a += (k[i][j]-k[i+1][j])**2
  a = sqrt(a)
  if a%1 == 0:
  ans += 1
print(ans)

### FIXED CODE ###

import math
N,D = map(int,input().split())
k = []
ans_2 = 0
ans_1 = 0
now = 0
for i in range(N):
    k.append(list(map(int,input().split())))
for i in range(0,N):
    for j in range(i+1,N):
        for _ in range(D):
            now += (k[i][_]-k[j][_])**2
        ans_1 = math.sqrt(now)
        if ans_1%1 == 0:
            ans_2 += 1
        now = 0
        ans_1 = 0
print(ans_2)
import sys
input = sys.stdin.readline

from math import factorial

def ncr(n, r):
    return factorial(n) / factorial(r) / factorial(n - r)

from collections import defaultdict

n = int(input())
d = defaultdict(lambda: 0)

for i in range(n):
    s = list(str(input()).rstrip())
    s.sort()
    s = "".join(s)
    d[s] += 1   

ans = 0
for key in d.keys():
    if d[key] >= 2:
        ans += ncr(d[key], 2)

print(int(ans))

### FIXED CODE ###

import sys
from collections import defaultdict
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


input = sys.stdin.readline

n = int(input())
d = defaultdict(lambda: 0)

for i in range(n):
    s = list(str(input()).rstrip())
    s.sort()
    s = "".join(s)
    d[s] += 1   

ans = 0
for key in d.keys():
    if d[key] >= 2:
        ans += cmb(d[key], 2)
print(int(ans))
,k = map(int,input().split())
a = 1
while k**a < n:
    a += 1

print(a)

### FIXED CODE ###

n,k = map(int,input().split())
a = 1
while k**a <= n:
    a += 1

print(a)