Harryxun/stf_run huggingface dataset:
#recording
N,C=map(int,input().split())
plus=[[0 for i in range(10**5+1)]for j in range(C+1)]
minus=[[0 for i in range(10**5+1)]for j in range(C+1)]
for _ in range(N):
    s,t,c=map(int,input().split())
    plus[c][s]=1
    minus[c][t+1]=-1
for c in range(1,C+1):
    for i in range(1,10**5+1):
        plus[c][i]+=plus[c][i-1]
        minus[c][i]+=minus[c][i-1]
ans=0
for i in range(10**5+1):
    sums=0
    for k in range(1,C+1):
        sums+=(plus[k][i]+minus[k][i])
    
    ans=max(sums,ans)
print(ans)

### FIXED CODE ###


N, C = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(N)]
 
record = [[0] * 10 ** 5 for _ in range(C)]
for s, t, c in stc:
    for i in range(s, t + 1):
        record[c-1][i-1] = 1
 
ans = 0
for i in range(10 ** 5):
    cnt = 0
    for j in range(C):
        cnt += record[j][i]
    ans = max(ans, cnt)
 
print(ans)
#!/usr/bin/env python3
#C
import numpy as np
import math
import re
import functools
def gcd_list(numbers):
    return functools.reduce(math.gcd, numbers)

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

m = 0
for i in range(n):
    s = []
    for j in range(n):
        if j != i:
            s.append(a[j])
    x = gcd_list(s)
    if(x > m):
        m = x
print(m)

### FIXED CODE ###

#!/usr/bin/env python3
#C
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

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

ans = 0
for i in range(N):
    ans = max(ans,gcd(L[i-1],R[i+1]))
print(ans)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
time=0
booka = 0
bookb = 0
booknum = 0
while True:
  if A[booka]<B[bookb]:
    time += A[booka]
    booka += 1
  else:
    time += B[bookb]
    bookb += 1
  if time>K:
    break
  booknum += 1
print(booknum)


### FIXED CODE ###

def getmax(x,y):
    if x>y:
        return x
    else:
        return y
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(N):   #a[i]にはAの本をi冊読んだ時の時間がそれぞれ保存されている．
    a.append(a[i]+A[i])  #計算量を減らすため，a[i]（1冊前までにかかる時間）を用いる
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j] > K-a[i]:    #Bの本を読んだ場合の処理はここで実行される．
        j -=1
    ans = max(ans, i+j)
print(ans)
A,B,C = map(int,input().split())
if B+C-A>=0
  print()
else print(0)

### FIXED CODE ###

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

if answer>=0:
  print(answer)
else :
  print(0)
def sumorder(k, a, b):
  a = list(str(k))
  s = sum(a)
  if a<=s and s<=b:
    return True
  else:
    return False
  
n, a, b = list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
  if sumorder(i, a, b):
    ans += i
    
print(ans)

### FIXED CODE ###

def sumorder(k, a, b):
  arr = list(str(k))
  s = sum(list(map(int,arr)))
  #print(arr, s)
  if a<=s and s<=b:
    return True
  else:
    return False
  
n, a, b = list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
  if sumorder(i, a, b):
    ans += i
    
print(ans)
N = int(input())
A = int(input())
B = int(input())
if N == 1:
    print("Hello World")
elif N ==2:
    print(A+B)

### FIXED CODE ###

N = int(input())
if N == 1:
    print("Hello World")
elif N ==2:
    A = int(input())
    B = int(input())
    print(A+B)
X = int(input())
for i in range(X+1):
  for p in range(X+1):
    ans = max(i ** p,ans)
print(str(ans))

### FIXED CODE ###

X = int(input())
ans = 0
for i in range(1,100):
  for p in range(2,100):
    tmp = i ** p
    if(tmp <= X):
      ans = max(tmp,ans)
    else:
      pass
print(str(ans))
N,M,C = map(int,input().split())
ab = {}
for i in range(N):
    a,b = map(int,input().split())
    if a in ab.keys():
        ab[a] += b
        continue
    ab[a] = b

keys = sorted(ab.keys())

ans = 0
kosu = 0
for k in keys:
    kosu += ab[k]
    if kosu >= M:
        kosu -= ab[k]
        break
    ans += k * ab[k]

for i in range(ab[k]):
    if kosu == M:
        break
    kosu += 1
    ans += k
print(ans)


### FIXED CODE ###

N,M,C = map(int,input().split())
B = list(map(int,input().split()))
A = []
for i in range(N):
    A.append(list(map(int,input().split())))

ans = 0
for i in range(N):
    tmp = 0
    for j in range(M):
        tmp += A[i][j]*B[j]
    tmp += C
    if tmp > 0:
        ans += 1
print(ans)
n = int(input())
a = list(map(int,input().split()))
c = 1
x = a[1]-a[0]
for i in range(1,n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 1
x = 0
for i in range(n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
    elif y!=0:x=y
print(c)
X=input()
t,s=0,0
for x in X:
 if x=='S':ns+=1
 elif ns>0:ns-=1
 else:nt+=1
print(nt+ns)

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())
N, M = map(int, input().split())

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

# 辞書データで管理
dict_cards = {}
for card in g_cards:
	if(card in dict_cards):
		dict_cards[card] += 1
	else:
		dict_cards[card] = 1
# 操作
for i in range(M):
	# sizeと同じ枚数のカードが増えたと考える
	size, val = map(int, input().split())
	if(val in dict_cards):
		dict_cards[val] += size
	else:
		dict_cards[val] = size

# 昇順にする
s_dict_cards = sorted(dict_cards.items(), key=lambda  x: -x[0])

# 取り出す
s_cards = []
for val, cnt in s_dict_cards:
	s_cards += [val] * cnt
	# 始めの個数を超えたら抜ける
	if(len(s_cards) >= N):
		break
# 出力
sum_val = sum(s_cards[:N])
print(sum_val)

### FIXED CODE ###

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

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

# key-valueデータで管理
dict_cards = []
for card in g_cards:
	dict_cards.append([card, 1])

# 操作
for i in range(M):
	# sizeと同じ枚数のカードが増えたと考える
	size, val = map(int, input().split())
	dict_cards.append([val, size])

# 降順にする
s_dict_cards = sorted(dict_cards, key=lambda x: -x[0])

s_cards = []
for data in s_dict_cards:
	s_cards += [data[0]] * data[1]
	if(len(s_cards) >= N):
		break
# 出力
sum_val = sum(s_cards[:N])
print(sum_val)
from bisect import bisect_left, bisect_right, insort_left

n = int(input())
s = input()
q = int(input())
qs = [list(input().split()) for _ in range(q)]

abc = [[-1, n] for _ in range(26)]
for i, e in enumerate(s):
    j = ord(e) - ord("a")
    abc[j].append(i)

for i in range(26):
    abc[i].sort()

for t, e1, e2 in qs:
    if t == "1":
        i = int(e1) - 1
        c = e2

        let = s[i]

        idx = ord(let) - ord("a")
        popi = bisect_left(abc[idx], i)
        abc[idx].pop(popi)

        idx = ord(c) - ord("a")
        insort_left(abc[idx], i)

    else:
        l = int(e1) - 1
        r = int(e2) - 1

        cnt = 0
        for i in range(26):
            li = bisect_left(abc[i], l)
            ri = bisect_right(abc[i], r)
            if li != ri:
                cnt += 1

        print(cnt)


### FIXED CODE ###

from bisect import bisect_left, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            if let == c:
                continue

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                if li >= len(abc[i]):
                    continue
                if abc[i][li] <= r:
                    cnt += 1

            print(cnt)


if __name__ == "__main__":
    main()
N,X=map(int,input().split())
x=list(map(int,input().split()))+[X]

from fractions import gcd

x=[x[i+1]-x[i] for i in range(N)]

def gcd_many(_list):
    if len(_list)==1:
        return abs(_list[0])
    elif len(_list)==2:
        return gcd(_list[0],_list[1])
    else:
        return gcd(_list[0],gcd_many(_list[1:]))
        
print(gcd_many(x))

### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))+[X]

from fractions import gcd

x=[x[i+1]-x[i] for i in range(N)]

ans=0
for i in range(N):
    ans=gcd(ans,x[i])
print(abs(ans))
import itertools
n = input()
x, pm, a = [], [1,-1], 7-int(n[0])
for i in range(1,4):
	x.append(int(n[i]))
for j in itertools.product(pm,repeat=3):
	if x[0]*j[0]+x[1]*j[1]+x[2]*j[2]==a:
		y = j
		break
for k in range(3):
	if y[k]==1: y[k] = "+"
	else: y[k] = "-"
print(n[0]+y[0]+n[1]+y[1]+n[2]+y[2]+n[3]+"=7")

### FIXED CODE ###

import itertools
n = input()
x, pm, a = [], [1,-1], 7-int(n[0])
for i in range(1,4):
	x.append(int(n[i]))
for j in itertools.product(pm,repeat=3):
	if x[0]*j[0]+x[1]*j[1]+x[2]*j[2]==a:
		y = list(j)
		break
for k in range(3):
	if y[k]==1:
		y[k] = "+"
	else:
		y[k] = "-"
print(n[0]+y[0]+n[1]+y[1]+n[2]+y[2]+n[3]+"=7")
import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = (1 << len(links)) - 1
    q = deque([(0, s, -1)])
    pop = q.popleft
    extend = q.extend
    while q:
        cost, v, p = pop()
        if cost > limit:
            break
        not_reachable ^= 1 << v
        cost += 1
        extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    link_list = []
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)
        link_list.append((a, b))

    limit = k // 2
    if k % 2 == 0:
        ans = min(bin(bfs(links, v, limit)).count('1') for v in range(n))
    else:
        dists = [bfs(links, v, limit) for v in range(n)]
        ans = min(bin(dists[a] & dists[b]).count('1') for a, b in link_list)
    return ans


n, k = map(int, sys.stdin.buffer.readline().split())
ab = map(int, sys.stdin.buffer.read().split())
ab = list(zip(ab, ab))
print(solve(n, k, ab))


### FIXED CODE ###

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))
a, b, c = input().split()
a = int(a)
b = int(b)
c = int(c)

if a == b && b != c:
  print("Yes")
  exit()
if a == c && b != c:
  print("Yes")
  exit()
if c == b && a != c:
  print("Yes")
  exit()

print("No")

### FIXED CODE ###

s = input().split()
a = int(s[0])
b = int(s[1])
c = int(s[2])

if a == b and b != c:
  print("Yes")
  exit()
if a == c and b != c:
  print("Yes")
  exit()
if c == b and a != c:
  print("Yes")
  exit()

print("No")
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def is_kaibun(_S):
    if _S[:int((len(_S)-1)/2)]==_S[int((len(_S)+1)/2):][::-1]:
        return True
    else:
        return False

def main():
    _S = S()
    is_tsuyoi1 = is_kaibun(_S)
    is_tsuyoi2 = is_kaibun(_S[:int((len(_S)-1)/2)])
    is_tsuyoi3 = is_kaibun(_S[int((len(_S)+3)/2)])
    print("Yes" if is_tsuyoi1 and is_tsuyoi2 and is_tsuyoi3 else "No")


main()


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def is_kaibun(_S):
    if len(_S)==1 or _S[:int((len(_S))/2)]==_S[int((len(_S)+1)/2):][::-1]:
        return True
    else:
        return False

def main():
    _S = S()
    is_tsuyoi1 = is_kaibun(_S)
    is_tsuyoi2 = is_kaibun(_S[:int((len(_S)-1)/2)])
    is_tsuyoi3 = is_kaibun(_S[int((len(_S)+1)/2):])
    print("Yes" if is_tsuyoi1 and is_tsuyoi2 and is_tsuyoi3 else "No")


main()
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    A = sorted(A)[::-1]
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    print(dp)
    array = find_array(dp,N,A)
    return "".join(map(str,array))

def fill(A,dp,n,N):
    cand = [ dp[n-num]+1 for num in A if n - num >= 0 ]
    dp[n] = max(cand) if len(cand) > 0 else -100*N

def find_array(dp,N,A):
    array = []
    sorted_A = sorted(A)
    print(sorted_A )
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A[::-1]:
            if dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    print(array)
                
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

### FIXED CODE ###

import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A:
            if current_n-RESOURCE_DICT[number] >= 0  and dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)
from decimal import Decimal
a,b=list(map(decimal,input().split()))
print(int(a*b))


### FIXED CODE ###

from decimal import Decimal
a,b=list(map(Decimal,input().split()))
print(int(a*b))
a=int(input())
b=｛25:"Christmas",24:"Christmas Eve",23:"Christmas Eve Eve",22:"Christmas Eve Eve Eve"｝
print(b[int(input())])

### FIXED CODE ###

b={25:"Christmas",24:"Christmas Eve",23:"Christmas Eve Eve",22:"Christmas Eve Eve Eve"}
print(b[int(input())])
N = int(input())
P = []
counter = 0
input_string = input()
P = input_string.split()

for i in range(N):
    for j in range(N):
        if N == int(P[i]):
            counter = counter + 1
            if N != 1:
                N = N - 1
                break
            else: 
                break
        elif N < int(P[i]):
            break
        else:
            if N != 1:
                N = N - 1   

print(counter)


### FIXED CODE ###

N, M = map(int, input().lower().split())

if N == M:
    print("Yes")
else:
    print("No")
x1,y1,x2,y2=map(int,input().split())
x=x2-x1
y=y2-y1
x3=x2-y
y3=y2+x
x4=x1-y
y4=y1+x
print(f'{x3} {y3} {x4} {y4}')

### FIXED CODE ###

# 2019/08/06

x1,y1,x2,y2=map(int,input().split())

xx=x2-x1
yy=y2-y1

x3=x2-yy
y3=y2+xx
x4=x1-yy
y4=y1+xx
print(x3,y3,x4,y4)
N=int(input())
A=list(map(int,input().split()))
X=1
if 0 in A:
  print(0)
  break

else:
  for idx in range(N):
  	X=X*A[idx]
  	if X >1*10**18:
   		print(-1)
    	break
	else:
  	print(X)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
X=1
if 0 in A:
    print(0)
else:
    for idx in range(N):
        X=X*A[idx]
        if X >10**18:
            print(-1)
            break
    else:
        print(X)
N,M = map(int(),input().split())
print('Yes' if N==M else 'No')

### FIXED CODE ###

N,M = input().split()
if N == M:
  print('Yes')
else:
  print('No')
n=int(input())
if n>=2 and n<=100:
    if n%2==0:
        print( (n/2)^2)
    else:
        print( ((n//2)+1)^2)


### FIXED CODE ###

import math

n = int( input())

print( math.ceil(n/2) * math.floor(n/2))
N, A, B = map(int, input().split())


li = [N*A,B]
print(min(li()))

### FIXED CODE ###

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

x = N*A
y = B

li = [x,y]
print(min(li))
N = input()
if N[1] == N[2] and N[2] == N[3]:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S = input()
if S[0] == S[1] and S[1] == S[2]:
  print("No")
else:
  print("Yes")
N = int(input())
A = list(map(int,input().split()))
count = [0] * N
#answer = [-1] * N
#p = [0] * N
for i in range(N):
  count[i]  = A.count(i + 1)
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)


### FIXED CODE ###

N, M = map(int, input().split())
gu = N * (N-1) //2
ki = M * (M-1) // 2
print(gu + ki)
S = input()
p = S.count('+')
m = s.count('-')
print(p-m)

### FIXED CODE ###

s = input()
p = s.count('+')
m = s.count('-')
print(p-m)
s=input()
cnt=0
ans="No"
flag=True

while cnt<len(s):
  if len(s)==1:
    flag=False
    break
  if s[cnt]=="h" and s[cnt+1]=="i":
    cnt+=2
    continue
  else:
    flag=False
    break
if flag:
  ans="Yes"
print(ans)

### FIXED CODE ###

s=input()
cnt=0
ans="No"
flag=True

while cnt<len(s):
  if len(s)==1 or len(s)%2==1:
    flag=False
    break
  if s[cnt]=="h" and s[cnt+1]=="i":
    cnt+=2
    continue
  else:
    flag=False
    break
if flag:
  ans="Yes"
print(ans)
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        self.table[s1] = s2
       
n = input()
uf=UnionFind3(n)
 

cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 print sum

### FIXED CODE ###

class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
uf=UnionFind3(100001)
 
n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 
print sum
N = int(input())
X = []
Y = []
Height =[] 
for i in range(N):
    x,y,h = map(int,input().split())
    X.append(x)
    Y.append(y)
    Height.append(h)
List = []
for Cx in range(101):
    for Cy in range(101):
        tmp_h = Height[0]+abs((X[0]-Cx))+abs((Y[0]-Cy))
        if tmp_h >= 1:
            List.append([Cx,Cy,tmp_h])

#1個目のx,y,hからCx,Cy,Hの候補を作り(List)，他のx,y,hは候補と照らし合わせながら答えを探す．
#制約が小さいからできる全探索

for i in range(1,N):
    for j in List[:]:
        if Height[i] == max(j[2]-abs((X[i]-j[0]))-abs((Y[i]-j[1])),0):
            continue
        else:
            List.remove(j)
print(List[0][0],List[0][1],List[0][2])

### FIXED CODE ###

N = int(input())
X = []
Y = []
Height =[] 
for i in range(N):
    x,y,h = map(int,input().split())
    X.append(x)
    Y.append(y)
    Height.append(h)
List = []
flag = 0
for i in range(N):
    if flag ==1:
        break
    if Height[i]==0:
        continue
    else:
        for Cx in range(101):
            for Cy in range(101):
                tmp_h = Height[i]+abs((X[i]-Cx))+abs((Y[i]-Cy))
                if tmp_h >= 1 :
                    List.append([Cx,Cy,tmp_h])
        flag = 1
     
    #1個目のx,y,hからCx,Cy,Hの候補を作り(List)，他のx,y,hは候補と照らし合わせながら答えを探す．
    #制約が小さいからできる全探索

for i in range(1,N):
    for j in List[:]:
        if Height[i] == max(j[2]-abs((X[i]-j[0]))-abs((Y[i]-j[1])),0):
            continue
        else:
            List.remove(j)

print(List[-1][0],List[-1][1],List[-1][2])
N = int(input(''))
if (N % 2) == 0:
  print(N/2N)
else:
  print((N+1)/2N)

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
  print(0.5000000000)
else:
  print((N+1)/(2*N))
N = int(input())
list = []
flag = True
for n in range(0, N):
  char = input()
  if n == 0:
    list.append(char)
  else:
    if char in list:
      flag = False
    else:
      list.append(char)
if flag == True:
  print('Yes')


### FIXED CODE ###

a, b = map(int, input().split())
for c in range(1, 4):
  if a*b*c % 2 == 1:
    print('Yes')
    break
  else:
    if c == 3:
      print('No')
N, M = map(int, input().split())

ab = [0] * M
for _ in range(M):
    a, b = map(int, input().split())
    ab[a].append(b)

dp = [0] * (N + 1)
for i in range(1, N + 1):
    dp[i] = max(dp[i], dp[i - 1])
    for j in ab[i]:
        dp[j] = max(dp[j], dp[i] + 1)

print(dp[N])


### FIXED CODE ###

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

ab.sort(key=lambda x: x[1])

result = 0
t = -1
for a, b in ab:
    a, b = a - 1, b - 1
    if a <= t < b:
        continue
    result += 1
    t = b - 1
print(result)
s = list(input())
j = -1

for i in range(len() // 2):
    if s[i] != s[j]:
        print('No')
        exit(0)

    j -= 1

print('Yes')


### FIXED CODE ###

s = list(input()) 
l = len(s) # l = 29
j = l - 1 # j = 28

for i in range(l // 2):
    if s[i] != s[j]:
        print('No')
        exit(0)
    j -= 1


h = (l + 3) // 2 - 1 # h = 15
j = h - 2

for h in range(l // 2):
    if s[h] != s[j]:
        print('No')
        exit(0)
    j -= 1

print('Yes')