Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*(n+1)
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)
h,w,a,b=map(int,input().split())
m=[[0]]
for i in range(w-1):
  s=min(m[0],key=lambda x:m[0].count(x))
  x=m[0].count(1-s)
  m[0]+=[1-s if x<a else s]
for i in range(h-1):
  n=[*zip(*m)]
  s=min(n[0],key=lambda x:n[0].count(x))
  x=n[0].count(1-s)
  m+=[[1-i for i in m[0]] if x<b else m[0]]

for i in m:
  print(*i)

### FIXED CODE ###

H, W, A, B = map(int, input().split())

arow = '1'*A + '0'*(W-A)
brow = '0'*A + '1'*(W-A)

for i in range(1,H+1):
    if (i <= B):
        print(brow)
    else:
        print(arow)
import copy
from math import gcd


# def gcd(a, b):
#     if b == 0:
#         return a
#     else:
#         return gcd(b, a%b)

def lcm(a, b):
    # return (a // gcd(a, b)) * b
    return (a * b) // gcd(a, b)
def main():
    n, m = map(int, input().split())
    # これだと72がREになる
    A = [int(x) for x in input().split()]
    # A_s = set(A)
    # A_ = copy.deepcopy(A)
    # a_lcm = A.pop()
    a_lcm = 1
    # Aの要素が複数ならlcmを計算する
    #if len(A) >= 1:
    for i in range(n):
        a_lcm = lcm(a_lcm, A[i])
    # mがlcmの半分よりも小さかったら0
    if (a_lcm / 2) > m:
    # if a_lcm > m * 2:
        print(0)
        exit()
    # for a in A:
    for i in range(n):
        # if a_lcm / 2 % A[i] == 0:
        if a_lcm // A[i] % 2 == 0: 
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
# from math import gcd


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a // gcd(a, b)) * b
def main():
    n, m = map(int, input().split())
    A = set([int(x) for x in input().split()])
    a_lcm = 1
    for a in A:
        a_lcm = lcm(a_lcm, a)
        # mがlcmの半分よりも小さかったら0
        if (a_lcm / 2) > m:
            print(0)
            exit()
    for a in A:
        if (a_lcm / 2) % a == 0:
            print(0)
            exit()
    # # あとは定数倍の数調べて終わり
    ans = int((m - (a_lcm / 2)) // a_lcm) + 1
    print(ans)

if __name__ == '__main__':
    main()
n, x = map(int, input().split())
l = [int(i) for i in input().split()]

i = 1
d = 0
c = 1
while True:
    d += l[i-1]
    if d > x or i == n + 1:
        break
    c += 1
    i += 1
    
print(c)

### FIXED CODE ###

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

count = 1
d = 0
for l in L:
    d += l
    if d > X:
        break
    count += 1
    
print(count)
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cb = []
for i in range(m):
    b,c = map(int, input().split())
    cb += [[c,b]]
cb = sorted(cb)[::-1]

def solve():
    p = 0
    q = 0
    ans = 0
    while p < n and q < m:
        if a[p] < cb[q][0]:
            if a [p + cb[q][1] - 1] < cb[q][0] and p + cb[q][1] - 1 < n:
                ans += cb[q][0] * cb[q][1]
                p = p + cb[q][1]
                q += 1
            else:
                for i in range(cb[q][1]):
                    if p + i == n:
                        return(ans)
                    elif a[p + i] < cb[q][0]:
                        ans += cb[q][0]
                    else:
                        ans += sum(a[p + i:])
                        return(ans)
        else:
            ans += sum(a[p:])
            return(ans)
    if q == n:
        return(ans)
    else:
        ans += sum(a[p:])
        return(ans)
print(solve())

### FIXED CODE ###

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

cb = []
for _ in range(m):
    b,c = map(int, input().split())
    cb.append([c, b])

a.sort()
cb.sort()

now = 0
finish = False
for i in range(m):
    b = cb[m - 1 - i][1]
    c = cb[m - 1 - i][0]
    for j in range(b):
        if now < n and a[now] < c:
            a[now] = c
            now += 1
        else:
            finish = True
            break
    if finish:
        break

print(sum(a))
a,b,c=map(str,input().split())

print('A'b[0]'C')

### FIXED CODE ###

a,b,c=map(str,input().split())
print('A'+b[0]+'C')
N = int(input())
A = list(map(int, input().split()))
S=sum(A)
i=0
X=0
while X<S/2:
    X=X+A[i]
    i=i+1
k=i
ka=0
ja=0
wa=0
ya=0
za=0
for l in range(k+2):
    ja=ja+A[l]
for l in range(k+1):
    ka=ka+A[l]
for l in range(k):
    wa=wa+A[l]
for l in range(k-2):
    ya=ya+A[l]
for l in range(k-1):
    za=za+A[l]
Z=[]
Z.append(abs(S-ja-ja))
Z.append(abs(S-ka-ka))
Z.append(abs(S-wa-wa))
Z.append(abs(S-ya-ya))
Z.append(abs(S-za-za))
print(min(Z))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S=sum(A)
i=0
X=0
while X<S/2:
    X=X+A[i]
    i=i+1
k=i
ka=0
ja=0
wa=0
ya=0
za=0
for l in range(k+1):
    ka=ka+A[l]
for l in range(k):
    wa=wa+A[l]
for l in range(k-1):
    za=za+A[l]
Z=[]

Z.append(abs(S-ka-ka))
Z.append(abs(S-wa-wa))

Z.append(abs(S-za-za))
print(min(Z))
S = input()
L = len(S)
A = [0 for i in range(L)]
f = 0
c = 0
P = 0
for i in range(L):
  if S[i] == "R":
    if f == 0:
      c += 1
    else:
      A[P] += c // 2
      A[P+1] += (c+1) // 2
      c = 1
      f = 0
  else:
    if f == 1:
      c += 1
    else:
      P = i-1
      A[P] += (c+1) // 2
      A[P+1] += c // 2
      c = 1
      f = 1
A[P] += c // 2
A[P+1] += (c+1) // 2
ans = str(A[0])
for i in range(1, N):
  ans = ans + " " + str(A[i])
print(ans)

### FIXED CODE ###

S = input()
L = len(S)
A = [0 for i in range(L)]
f = 0
c = 0
P = 0
for i in range(L):
  if S[i] == "R":
    if f == 0:
      c += 1
    else:
      A[P] += c // 2
      A[P+1] += (c+1) // 2
      c = 1
      f = 0
  else:
    if f == 1:
      c += 1
    else:
      P = i-1
      A[P] += (c+1) // 2
      A[P+1] += c // 2
      c = 1
      f = 1
A[P] += c // 2
A[P+1] += (c+1) // 2
for a in A:
  print(a)
def s(way):
    global w
    global c
    for i in way:
        if c[i] == 0:
            c[i] = 1
            s(w[i])

from collections import deque

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

w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    w[a-1].append(b-1)
    w[b-1].append(a-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])
print(ans)

### FIXED CODE ###


from collections import deque

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

w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    w[a-1].append(b-1)
    w[b-1].append(a-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        d.append(i)
        while d:
            x = d.pop()
            for i in w[x]:
                if c[i] == 0:
                    c[i] = 1
                    d.append(i)

print(ans)
n = input()
if n[-1] == '2' or '4' or '5' or '7' or '9':
    print('hon')
elif n[-1] == '0' or '1' or '6' or '8':
    print('pon')
else print('bon'):
    print('bon')

### FIXED CODE ###

n = input()
if n[-1] == '2' or n[-1] == '4' or n[-1] == '5' or n[-1] =='7' or n[-1] == '9':
    print('hon')
elif n[-1] == '0' or n[-1] == '1' or n[-1] == '6' or n[-1] == '8':
    print('pon')
else:
    print('bon')
for i in range(1,10100):
    if int(i*0.08)==A and int(i*0.1)==B:
        print(i)
        break
else:
    print(-1)

### FIXED CODE ###

A,B = map(int,input().split())

for i in range(1,10100):
    if int(i*0.08)==A and int(i*0.1)==B:
        print(i)
        break
else:
    print(-1)
A = int(input())
B = int(input())
C = int(input())

if A+B+C == 17 and A*B*C == 175:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

if A+B+C == 17 and A*B*C == 175:
    print('YES')
else:
    print('NO')
import numpy as np

from sys import exit

def main():
  A, B = map(int, input().split(' '))
  values = range(A, B+1)
  # values = []

  # for n in N:
  #   values.append('{:043b}'.format(n))

  values = np.array(values)
  for i, value in enumerate(values):
    if i == 0:
      result = value
    else:
      result = np.bitwise_xor(result, value)
  print(int(result))
    
  # if len(values) == 1:
  #   print(int(values[0], 2))
  #   return

  # result = ''

  # if len(values) % 2 == 1:
  #   for n in range(43):
  #     num_zero = 0
  #     for value in values:
  #       if value[n] == '0':
  #         num_zero += 1

  #     if num_zero % 2 == 0:
  #       result += '1'
  #     else:
  #       result += '0'

  # else:
  #   for n in range(43):
  #     num_zero = 0

  #     for value in values:
  #       if value[n] == '0':
  #         num_zero += 1

  #     if num_zero % 2 == 0:
  #       result += '0'
  #     else:
  #       result += '1'
  # print(int(result, 2))
  
main()



### FIXED CODE ###

def main():
  H, W = map(int, input().split(' '))
  h, w = map(int, input().split(' '))
  
  a = H*W
  b = (h * W) + (w * H) - h * w
  print(a - b)
  


main()
def main():
    W, H = map(i,input().split())
    h, w = map(i,input().split())

    point = W * H

    delete_h = h * W
    delete_w = w * H

    kaburi = h * w

    ans = point - (delete_h + delete_w - kaburi)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int,input().split())
    h, w = map(int,input().split())

    point = W * H

    delete_h = h * W
    delete_w = w * H

    kaburi = h * w

    ans = point - (delete_h + delete_w - kaburi)
    print(ans)


if __name__ == '__main__':
    main()
s=list(input())
count1=0
count2=0
for i in range(len(s)):
  if s[i]==s[i+1]:
    count1=count1+1
for i in range(1,len(s)):
  if s[i]==s[i+1]:
    count2=count2+1
if count1>=count2:
  print(count1)
else:
  print(count2)

### FIXED CODE ###

s=list(input())
count1=0
count2=0
for i in range(len(s)-1):
  if s[i]==s[i+1]:
    count1=count1+1
    if s[i+1]=='0':
      s[i+1]='1'
    else:
      s[i+1]='0'
for i in range(1,len(s)-1):
  if s[i]==s[i+1]:
    count2=count2+1
    count1=count1+1
    if s[i+1]=='0':
      s[i+1]='1'
    else:
      s[i+1]='0'
if count1>=count2:
  print(count1)
else:
  print(count2)
MAX_INT = 10**6
N, M = map(int, input().split())
room = [set() for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    room[a].add(b)
    room[b].add(a)

dis = [MAX_INT] * (N + 1)
sign = [-1] * (N + 1)
dis[1] = 0
def sign_root(n):
    for i in room[n]:
        if dis[n] + 1 < dis[i]:
            sign[i] = n
            dis[i] = dis[n] + 1
            sign_root(i)
sign_root(1)
if MAX_INT in dis[2:]:
    print("No")
else:
    print("Yes")
    for i in sign[2:]:
        print(i)

### FIXED CODE ###

MAX_INT = 10**6
N, M = map(int, input().split())
room = [set() for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    room[a].add(b)
    room[b].add(a)

dis = [MAX_INT] * (N + 1)
sign = [-1] * (N + 1)
dis[1] = 0
def sign_root(n):
    nxt = []
    for i in room[n]:
        if dis[n] + 1 < dis[i]:
            sign[i] = n
            dis[i] = dis[n] + 1
            nxt += [i]
    return nxt

nxt = sign_root(1)
while nxt != []:
    for i in nxt.copy():
        nxt.pop(0)
        nxt += sign_root(i)
if MAX_INT in dis[2:]:
    print("No")
else:
    print("Yes")
    for i in sign[2:]:
        print(i)
N=(input())
a = len(N)
if a>=3:
    x = int(N[a-3]+N[a-2]+N[a-1])
    print(1000-x)
elif a=2:
    x = int(N[a-2]+N[a-1])
    print(1000-x)
else :
    x = int(N[a-1])
    print(1000-x)

### FIXED CODE ###

N=int((input()))

if N%1000==0:
    print(0)
    
else:
  N=str(N)
  a = len(N)
  if a>=3:
        x = int(N[a-3]+N[a-2]+N[a-1])
        print(1000-x)
  elif a==2:
        x = int(N[a-2]+N[a-1])
        print(1000-x)
  else :
        x = int(N[a-1])
        print(1000-x)
n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(j-y)),abs(y-i)+1+abs(j-x)-1]+=1
for i in range(n-1):
    print(ans[i])


### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))-1]+=1
for i in range(n-1):
    print(ans[i])
k, x = [int(x) for x in input().split()]
print(" ".join(range(x - k + 1, x + k - 1)))

### FIXED CODE ###

k, x = [int(x) for x in input().split()]
print(" ".join(str(i) for i in range(x - k + 1, x + k)))
n,m,*x = map(int,open(0).read().split())
x.sort()
if m == 1:
  print(0)
  exit()
a = sorted([x[i+1]-x[i] for i in range(m-1)],reverse=True)
ans = x[-1]-x[0]
for i in range(n-1):
  ans -= a[i]
print(ans)

### FIXED CODE ###

n,m,*x = map(int,open(0).read().split())
x.sort()
if n >= m:
  print(0)
  exit()
a = sorted([x[i+1]-x[i] for i in range(m-1)],reverse=True)
ans = x[-1]-x[0]
for i in range(n-1):
  ans -= a[i]
print(ans)
a,b,c=map(int,input().split())
if a >= c:
  print(a-c,0)
else:
  print(0.max(a+b-c,0))

### FIXED CODE ###

a,b,c=map(int,input().split())
if a >= c:
  print(a-c,b)
else:
  print(0,max(a+b-c,0))
import sys
sys.setrecursionlimit(1000000000)

n,u,v = map(int,input().split())
u -= 1
v -= 1
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

dist = [-1]*n
dist[v] = 0
prev = [-1]*n
def dfs(now):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        prev[nxt] = now
        dfs(nxt)
dfs(v)

color = [0]*n
now = u
while now >= 0:
    color[now] = 1
    now = prev[now]

def dfs2(now,prev,dist,cnt):
    if dist == 0: return cnt
    if dist == -1: return cnt-1
    if G[now] == [prev]: return cnt+dist-1
    res = 0
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt]: res = max(res,dfs2(nxt,now,dist-2,cnt+1))
        else: res = max(res,dfs2(nxt,now,dist,cnt+1))
    return res

print(dfs2(u,-1,dist[u]-dist[v],0))

### FIXED CODE ###

n = int(input())

if n%2 != 0:
    ans = 0
else:
    ans = 0
    x = 5
    while n >= x:
        ans += n//(x*2)
        x *= 5

print(ans)
c1 = input()
c2 = input()

if c1.reverse() == c2:
  print('YES')
else:
  print('NO')


### FIXED CODE ###

c1 = input()
c2 = input()

if c1[2] + c1[1] + c1[0] == c2:
  print('YES')
else:
  print('NO')
X=int(input())
if X==2:
  print(X)
else:
  for i in range(2,X**(1/2)):
    if X%i==0:
      X+=1
  print(X)


### FIXED CODE ###

import math
X=int(input())
while True:
    for i in range(2,int(math.sqrt(X))+1):
      if X%i==0:
        X+=1
        break
    else:
      print(X)
      break
S = list(input())
S[3] = "8"
print("".join(S))


### FIXED CODE ###

S = list(input())
S[3] = "8"
print("".join(S))
r = int(input())
import math
print(math.pi*r**2,2*math.pi*r)

### FIXED CODE ###

r = float(input())
pi = 3.14159265359
print("{:f}".format(pi*r**2),"{:f}".format(2*pi*r))
s = input()
K = int(input())
ans = []
for i in set(s):
    ans.append(i)

if K == 1:
    print(sorted(ans)[0])
else:
    for i in range(2, 6):
        for j in range(len(s) - i + 1):
            ans.append(s[j:j+i])
    ans = set(ans)
    ans.sort()
    print(ans[K - 1])

### FIXED CODE ###

s = input()
K = int(input())
one = list(set(s))
check = 2
if len(s) >= 2:
    while check <= len(s) and check <= 5:
        for i in range(len(s) - check + 1):
            one.append(s[i:i+check])
        check += 1
    one = sorted(set(one))
    print(one[K-1])
    
     
else:
    one = sorted(one)
    print(one[K-1])
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
ans = []
 
for n in range(N):
  i = N-n
  BB = B[::i]
  if (sum(BB))%2 != A[i-1]:
    B[i] = 1
    ans.append(str(i))
  
print(len(x))
print(' '.join(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0 for n in range(N+1)]
x = []

for n in range(N):
  i = N-n
  # print(i)
  BB = B[::i]
  if (sum(BB))%2 == A[i-1]:
    B[i] = 0
  else:
    B[i] = 1
    # print(B)
  if B[i] == 1:
    x.append(str(i))
  
if len(x) == 0:
  print(0)
else:
  print(len(x))
  print(' '.join(x))
A = input()
for i in range(1, A+1):
    if i == A:
        print("x")
    else:
        print("x", end="")

### FIXED CODE ###

A = input().strip()
n = len(A)
for i in range(1, n+1):
    if i == n:
        print("x")
    else:
        print("x", end="")
N = int(input())
S = []
for i in range(N):
    s = str(input())
    s = ''.join(sorted(a))
    S.append(s)

count = 0
for i in range(N):
    Si = S[i]
    for k in range(N):
        if i==k:
            None
        Sk = S[k]
        if Sk == Si:
            count += 1

print(count / 2)


### FIXED CODE ###

"""自分で考えたやつ

N = int(input())
S = []
for i in range(N):
    s = str(input())
    s = ''.join(sorted(s))
    S.append(s)

count = 0
for i in range(N):
    Si = S[i]
    for k in range(N):
        if i==k:
            None
        else:
            Sk = S[k]
            if Sk == Si:
                count += 1

print(count / 2)
"""

N = int(input())
dic = {}
ans = 0

for i in range(N):
    s = ''.join(sorted(input()))
    if s in dic:
        ans += dic[s]
        dic[s] += 1
    else:
        dic[s] = 1
print(ans)
T=input()
n=len(t)
i=r=a=0
for c in T:
  k=i-r
  if c=='0':
    r+=k&1
  else:
    a+=i//2-k//2+(k&1)*(n-i)
  i+=1
print(a)

### FIXED CODE ###

t=input()
n=len(t)
pos=[]
sum=0
for i in range(n):
  if t[i]=="1":
    sum+=1
  else:
    pos.append(sum)
x=(sum+1)//2*((sum+2)//2)
sz=len(pos)
cnt=0
res=[]
for i in range(sz):
  if ((pos[i]&1)^(cnt&1)):
    sum+=1
    cnt+=1
    x+=(sum+1)//2
  else:
    res.append(i)
res=res[::-1]
odd=0
even=0
for i in range(len(res)):
  sum+=1
  if i&1:
    odd = sz - res[i] - even
    x+=(sum+1)//2-odd
  else:
    even=sz-res[i]-odd
    x+=(sum+1)//2-even
print(x)
k,s = map(int,input().split())
Xm = k
Ym = k
Zm = k
count = 0
for i in range(Xm+1):
  for j in range(Ym+1):
    for m in range(Zm+1):
      if i+j+m = s:
        count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
Xm = k
Ym = k
Zm = k #使わない
count = 0
for i in range(Xm+1):
  for j in range(Ym+1):
    if 0<= s - (i+j) <= k:
        count += 1
print(count)
K, X = (int, input().split())
print("Yes") if 500*K>X else print("No")

### FIXED CODE ###

K, X = map(int, input().split())
print("Yes") if 500 * K >= X else print("No")
# -*- coding: utf-8 -*-
import sys
k=int(input())
n=-1
if k%2==0:
  print(n)
  sys.exit()
l=1
while True:
  s=(7*(10**l-1))/9
  if s%k==0:
    print(l)
    break
  l+=1

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
k=int(input())
if k%2==0 or k%5==0:
  print(-1)
  sys.exit()
s=7
for i in range(k):
  m=s%k
  if m==0:
    print(i+1)
    break
  s=m*10+7
n,m=(int(i) for i in input().split())
a=0
b=0
for i in range(m):
  l,r=(int(j) for j in input().split())
  if l>a and r<b:
    a=l
    b=r
  elif l>a and r>=b:
    a=l
  elif r<b and l<=a:
    b=r
if b>=a:
	if n>a and n<b:
  		t=n-a+1
        print(t)
	elif n>a and n>=b:
  		t=b-a+1
        print(t)
	else:
  		print(0)
else:
  print(0)


### FIXED CODE ###

a,b=(int(i) for i in input().split())
if a<=5:
  print(0)
elif 5<a<=12:
  print(b//2)
else:
  print(b)
number = input().split()

for i in number:
 sum = sum + i
 
if(sum>21): 
 print("bust")
else:
 print("win")


### FIXED CODE ###

number = list(map(int, input().split())) 

sum = 0
for i in number:
 sum += i
 
if(sum>21): 
 print("bust")
else:
 print("win")
N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
if 1 not in broken:
    memo[1] = 1
else:
    memo[1] = 0
if 2 not in broken:
    if 1 not in broken:
        memo[2] = 2
    else:
        memo[2] = 1
else:
    memo[2] = 0
for i in range(3, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])


### FIXED CODE ###

N, M = map(int, input().split())
broken = set()
for _ in range(M):
    a = int(input())
    broken.add(a)

INF = 10 ** 9 + 7

memo = [None for _ in range(N + 1)]
memo[0] = 1
memo[1] = 0 if 1 in broken else 1
for i in range(2, N + 1):
    if i in broken:
        memo[i] = 0
    else:
        memo[i] = (memo[i - 2] + memo[i - 1]) % INF

print(memo[N])
# -*- coding utf-8 -*-
import numpy as np

MOD = 10 ** 9 + 7

n = int(input())

# graph = [[-1] * n for _ in range(n)]
graph = np.zeros((n, n), dtype=np.int64)
graph -= 1
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j in range(n):
        if dist[j] == -1 and graph[i][j] != -1:
            dist[j] = dist[i] + graph[i][j]
            que.append(j)

for d in dist:
    print(d % 2)



### FIXED CODE ###

# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

n = int(input())

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u - 1].append((v - 1, w))
    graph[v - 1].append((u - 1, w))

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j, w in graph[i]:
        if dist[j] == -1:
            dist[j] = dist[i] + w
            que.append(j)

for d in dist:
    print(d % 2)
n = int(input())
x = []
y = []
for i in range(n):
  _x, _y = map(int, input().split())
  x.append(_x)
  y.append(_y)
#それぞれの組み合わせに対して2*(n-1)!回ずつ合計に加算される→平均への寄与は2/n倍
def d(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

ans = 0
for i in range(n):
  for j in range(i+1, n):
    ans += d(x[i], y[i], x[j], y[j])
print(ans*2/n)


### FIXED CODE ###

print((int(input()))**2)