Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc126/tasks/abc126_d

import sys

def dfs(i):
  for v,w in V.get(i, []):
    if (w % 2) == 0:
      if color[v] == -1:
        color[v] = color[i]
      elif color[v] == color[i]:
        continue
      elif color[v] != color[i]:
        return False
    else:
      if color[v] == -1:
        color[v] = 0 if color[i] else 1
      elif color[v] == color[i]:
        return False
      elif color[v] != color[i]:
        continue
    dfs(v)
  return True

if __name__ == '__main__':
  n = int(input())
  V = {} # key:vertex, value:[[vertex opposited, wight]]
  color = {} # 0 or 1 or -1
  for i in range(1, n):
    u,v,w = map(int, input().split())
    if not V.get(u, False):
      V[u] = [[v,w]]
    else:
      V[u].append([v,w])

    if not V.get(v, False):
      V[v] = [[u,w]]
    else:
      V[v].append([u,w])
    # 同じ頂点間で複数の辺はないと仮定
  for i in range(1, n+1):
    color[i] = -1

  i = 1
  color[i] = 0
  while dfs(i):
    for j in range(1, n+1):
      if color[j] == -1:
        i = j
        color[j] = 0
        break
    for j in range(1, n+1):
      print(color[j])
    sys.exit()
  print('No')  
  

### FIXED CODE ###

# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc126/tasks/abc126_d

import sys
sys.setrecursionlimit(100000)

def dfs(i):
  for v,w in V.get(i, []):
    if (w % 2) == 0:
      if color[v] == -1:
        color[v] = color[i]
      elif color[v] == color[i]:
        continue
      elif color[v] != color[i]:
        return False
    else:
      if color[v] == -1:
        color[v] = 0 if color[i] else 1
      elif color[v] == color[i]:
        return False
      elif color[v] != color[i]:
        continue
    dfs(v)
  return True

if __name__ == '__main__':
  n = int(input())
  V = {} # key:vertex, value:[[vertex opposited, wight]]
  color = {} # 0 or 1 or -1
  for i in range(1, n):
    u,v,w = map(int, input().split())
    if not V.get(u, False):
      V[u] = [[v,w]]
    else:
      V[u].append([v,w])

    if not V.get(v, False):
      V[v] = [[u,w]]
    else:
      V[v].append([u,w])
    # 同じ頂点間で複数の辺はないと仮定
  for i in range(1, n+1):
    color[i] = -1

  while True:
    i = 0
    for j in range(1, n+1):
      if color[j] == -1:
        i = j
        color[i] = 0
        break
    if i == 0:
      for j in range(1, n+1):
        print(color[j])
      break
    else:
      if not dfs(i):
        print('No')
        break
N = int(input())
li = list(map(int, input().split()))
ans = "Yes"
count = N - 1
while count >= 0:
    if li[count] - li[count-1] => 0:
        pass
    elif li[count] - li[count-1] = -1:
        li[count-1] -= 1
    else:
        ans = "No"
        break
    count -= 1
print(ans)

### FIXED CODE ###

N = int(input())
li = list(map(int, input().split()))
ans = "Yes"
count = N - 1
while count >= 1:
    if li[count] - li[count-1] >= 0:
        pass
    elif li[count] - li[count-1] == -1:
        li[count-1] -= 1
    else:
        ans = "No"
        break
    count -= 1
print(ans)
a = int(input())
b = int(input())
c = int(input())
d = int(input())

num_listx = []
num_listy = []

for num in range(b + 1):
  if num >= a:
    num_listx.append(num)
for nums in range(d + 1):
  if nums >= c:
    num_listy.append(nums)
x = max(num_listx)
y = max(num_listy)
print(x*y)


### FIXED CODE ###

a,b,c,d = map(int,input().split())

ans = max(a*c,a*d,b*c,b*d)

print(ans)
n = input()
a = n%1000
if a == 1000:
  print(0)
else:
  print(a)

### FIXED CODE ###

n = int(input())
a = n%1000
if a == 0:
  print(0)
else:
  print(1000 - a)
n = int(input())
s = [int(input()) for i in range(n)]
s.sort()
j = sum([ i % 10 for i in s ])
if j == 0:
    ans = 0
else:
    for i in range(n):
        tmp = sum(s)-s[i]
        if tmp % 10 != 0:
            ans = tmp
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = [int(input()) for i in range(n)]
s.sort()
j = sum([ i % 10 for i in s ])
if j == 0:
    ans = 0
else:
    if sum(s) % 10 != 0:
        ans = sum(s)
    else:
        for i in range(n):
            tmp = sum(s)-s[i]
            if tmp % 10 != 0:
                ans = tmp
                break
print(ans)
import unittest
import abc123d as tester

def ioByFile(fn='inputFile.txt'):
	with open(fn) as f:
		for line in f:
			yield line

def getCorrect(fn='correct.txt'):
	with open(fn) as f:
		return f.read()

class InputTests(unittest.TestCase):
	def _calFUT(self, io):
		return str(tester.main(io))+'\n'
		
	def test_it(self):
		testInput=ioByFile()
		io=lambda : next(testInput)
		actual = self._calFUT(io)
		
		self.assertEqual(actual,getCorrect())

if __name__ == "__main__":
	unittest.main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

from heapq import heappush, heappop
def io_generator():
	return input()

#+++++++++++++++++++
	
class Foo(object):
	def __init__(self, value, state):
		self.state = state
		self.value = value

	def __lt__(self, other):
		return self.value > other.value

def get_c(aa,ab,ac, amm):
	if ac < amm[2]-1:
		ret=[[aa,ab,ac+1]]
	else:
		ret=[]
		
	if ab<amm[1]-1:# and ab >= ac:
		ret.append([aa,ab+1,ac])
	
	if aa<amm[0]-1:# and aa >= ab and aa >= ac:
		ret.append([aa+1,ab,ac])
	return ret
	
def gv(al,bl,cl,s):
	return al[s[0]]+bl[s[1]]+cl[s[2]]
	
def lss(l):
	return '_'.join([str(i) for i in l])
	
def main(io):
	x,y,z,k=map(int, io().split())
	ml=[x,y,z]
	al =list(map(int, io().split()))
	al.sort(reverse=True)
	bl =list(map(int, io().split()))
	bl.sort(reverse=True)
	cl =list(map(int, io().split()))
	cl.sort(reverse=True)
	init=[0,0,0]
	ggv=lambda l : gv(al,bl,cl,l)
	
	qq = []
	heappush(qq,Foo(ggv(init), init))
	
	ol=set()
	ol.add(lss(init))
	
	for _ in range(k):
		ff=heappop(qq)
		vv=ff.value
		cs=ff.state
		nc=get_c(cs[0],cs[1],cs[2],ml)
		print(vv)
		for ns in nc:
			if lss(ns) in ol:
				continue
			else:
				heappush(qq, Foo(ggv(ns), ns))
				ol.add(lss(ns))
	return 1

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	#print (main(io))
	main(io)
a,b = raw_input()
a,b = input(a,b)
print a*b, 2*a+2*b

### FIXED CODE ###

a, b = map(int, raw_input(). split())
print a * b, 2 * (a + b)
A1 = input()
A2 = input()
A3 = input()


### FIXED CODE ###

a,b,c=map(int,input().split())
if a+b+c >= 22:
  print("bust")
else:
  print("win")
N = int(input())

if (N >= 1) & (N <= 999)
    print('ABC')
else:
    print('ABD')

### FIXED CODE ###

N = int(input())

if (N >= 1) and (N <= 999):
    print('ABC')
else:
    print('ABD')
a,s=map(int,input(),split())
print(max(a-2*s,0))

### FIXED CODE ###

a,s=map(int,input().split())
print(max(a-2*s,0))
a=input()
b=input()
count=0
for str_i in range (len(a)):
	if a[str_i] != b[str_i]:
      count+=1
print(count)

### FIXED CODE ###

S=input()  
T=input()
num = 0
for i in range(len(S)):
	if S[i] != T[i]:
		num= num+1
print(num)
import sys

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

for i in range(1,N):
    if A[i]<=A[i-1]:
        break
else:
    print(1)
    sys.exit()

kind=2
ketadict=dict()
ketadict[A[i]]=kind

for i in range(i+1,N):
    #print(i,ketadict,kind)
    if A[i]>A[i-1]:
        ketadict[A[i]]=1
        continue

    if ketadict.get(A[i],1)!=kind:
        ketadict[A[i]]=ketadict.get(A[i],1)+1
        continue

    if ketadict.get(A[i],1)==kind:
        x=A[i]
        while ketadict.get(x,1)==kind:
            ketadict[x]=1
            x-=1
        if x!=0:
            ketadict[x]=ketadict.get(x,1)+1
            for j in ketadict.keys():
                if j>x:
                    del ketadict[j]
        else:
            kind+=1
            ketadict=dict()
            ketadict[1]=kind
    
print(max(ketadict.values()))



### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict

N=int(input())
A=[0]+list(map(int,input().split()))

def Nextstring(nowlength,nextlength):
    if nextlength>nowlength:
        while -USELIST[0]>nowlength:
            dis=-heapq.heappop(USELIST)
            del NOWSTR[dis]
        nowlength=nextlength

    else:
        while -USELIST[0]>nextlength:
            dis=-heapq.heappop(USELIST)
            del NOWSTR[dis]

        if NOWSTR[nextlength]<mid-1:
            
            if NOWSTR[nextlength]==0:
                NOWSTR[nextlength]+=1
                heapq.heappush(USELIST,-nextlength)
                nowlength=nextlength
            else:
                NOWSTR[nextlength]+=1
                nowlength=nextlength

        else:
            klength=nextlength
            while NOWSTR[klength]==mid-1:
                if klength in NOWSTR:
                    del NOWSTR[klength]
                klength-=1
                if mid!=1:
                    dis=-heapq.heappop(USELIST)
                    if dis in NOWSTR:
                        del NOWSTR[dis]

                if klength==0:
                    return -1

            if NOWSTR[klength]==0:
                NOWSTR[klength]+=1
                heapq.heappush(USELIST,-klength)
                nowlength=nextlength

            else:
                NOWSTR[klength]+=1
                nowlength=nextlength

    return 0

for i in range(N):
    if A[i]>=A[i+1]:
        MIN=2
        break
else:
    print(1)
    sys.exit()

from collections import Counter
MAX=max(Counter(A).values())+1

while MIN!=MAX:
    mid=(MIN+MAX)//2
    nowlength=0
    NOWSTR=defaultdict(int)
    USELIST=[10**6]

    for i in range(N):

        if Nextstring(A[i],A[i+1])==-1:
            MIN=mid+1
            break
        #print(mid,NOWSTR,USELIST)
    else:
        MAX=mid

print(MIN)
import collections

def int_cards(N, cards, operations):
    col_cards = collections.deque(sorted(cards), N)
    operations.sort(reverse=True)
    for c, b in operations:
        for _ in range(b):
            if col_cards[0] >= c:
                break
            col_cards.popleft()
            col_cards.append(c)
            
    print(sum(col_cards))
    
N, M = map(int, input().split())
A = list(map(int,input().split()))
operations = []
for i in range(M):
    B, C = map(int, input().split())
    operations.append([C, B])
    
int_cards(N, A, operations)

### FIXED CODE ###

def ferris_wheel(age, cost):
    if age <= 5:
        print(0)
    elif age <= 12:
        print(int(cost / 2))
    else:
        print(cost)
        
a, b = map(int, input().split())
ferris_wheel(a, b)
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)
s = input()
ans = False
if s[0] == s[1] :
  if s[0] != s[2] and s[2] ==s[3] :
  ans = True
elif s[0] == s[2] :
  if s[0] != s[1] and s[1] ==s[3] :
  ans = True
else s[0] == s[3] :
  if s[0] != s[1] and s[2] ==s[1] :
  ans = True
if ans :
  print('Yse')
else:
  print('No')

### FIXED CODE ###

s=input()
ans=False
if s[0]==s[1]:
    if s[0]!=s[2] and s[2]==s[3]:
        ans=True
elif s[0]==s[2]:
    if s[0]!=s[1] and s[1]==s[3]:
        ans=True
elif s[0]==s[3]:
    if s[0]!=s[1] and s[1]==s[2]:
        ans=True
if ans:
    print('Yes')
else:
    print('No')
N = int(input())
S = [[int(i) for i in input().split()] for j in range(N)]
SS = sorted(S,key=lambda x: x[2], reverse=True)

#(x, y)を(0,0)から(100,100)まで試す
def firstlook(si, kohod): 
    for x in range(0, 100+1):
        for y in range(0, 100+1):
            h = max((si[2]+abs(si[0]-x)+abs(si[1]-y)),0)
            kohod[(x,y)] = h
    return kohod

def lastlook(si, kohod):
    for (x, y) in list(kohod.keys()):
        h = max((si[2]+abs(si[0]-x)+abs(si[1]-y)),0)
        if kohod[(x,y)] != h:
            del kohod[(x,y)]
    return kohod

anspre = firstlook(SS[0], dict())
for Si in SS:
    ans = lastlook(Si, anspre)

[xy] = list(ans.keys())
print(str(xy[0]) + " " + str(xy[1]) + " "+ str(ans[xy]))

### FIXED CODE ###

N = int(input())
S = [[int(i) for i in input().split()] for j in range(N)]
SS = sorted(S,key=lambda x: x[2], reverse=True)

#(x, y)を(0,0)から(100,100)まで試す
def firstlook(si, kohod): 
    for x in range(0, 100+1):
        for y in range(0, 100+1):
            h = si[2]+abs(si[0]-x)+abs(si[1]-y)
            kohod[(x,y)] = h
    return kohod

def lastlook(si, kohod):
    for (x, y) in list(kohod.keys()):
        h = max(kohod[(x,y)]-abs(si[0]-x)-abs(si[1]-y),0)
        if si[2] != h:
            del kohod[(x,y)]
    return kohod

ans = firstlook(SS[0], dict())
for Si in SS[1:]:
    ans = lastlook(Si, ans)

[xy] = list(ans.keys())
print(str(xy[0]) + " " + str(xy[1]) + " "+ str(ans[xy]))
S = input()
h = int(S / 3600)
m = int(h % 3600 / 60)
s = int(S % 60)

print(h,m,s,sep = ':')

### FIXED CODE ###

S = int(input())
h = int(S / 3600)
m = int(S % 3600 / 60)
s = int(S % 60)
print(h, m, s, sep=':')
mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

neg = []
zero = 0
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)

pos.sort()
neg.sort(reverse=True)

if len(pos) == 0:
    res = 1
    A = A[:K] if K % 2 == 1 else A[-K:]
    for a in A:
        res *= a
        res %= mod
else:
    res = 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)

### FIXED CODE ###

mod = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

neg = []
zero = 0
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)

pos.sort()
neg.sort(reverse=True)

if len(pos) == 0:
    res = 1
    if K % 2 == 0:
        neg.reverse()
    for a in neg[:K]:
        res *= a
        res %= mod
else:
    res = 1
    if K % 2 == 1:
        res = pos.pop()
        K -= 1
    while K > 1 and len(pos) > 1 and len(neg) > 1:
        if pos[-1] * pos[-2] > neg[-1] * neg[-2]:
            res *= pos.pop()
            res %= mod
            res *= pos.pop()
            res %= mod
        else:
            res *= neg.pop()
            res %= mod
            res *= neg.pop()
            res %= mod
        K -= 2
    while K > 1 and len(pos) > 1:
        res *= pos.pop()
        res %= mod
        res *= pos.pop()
        res %= mod
        K -= 2
    while K > 1 and len(neg) > 1:
        res *= neg.pop()
        res %= mod
        res *= neg.pop()
        res %= mod
        K -= 2
    while K and pos:
        res *= pos.pop()
        res %= mod
        K -= 1
    while K and neg:
        res *= neg.pop()
        res %= mod
        K -= 1


print(res)
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
n=int(input())
a=list(map(int,input().split()))

b=lcm_list(a)-1
ans=0
for i in a:
    tmp=b%i
    ans+=tmp
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
x=1
for t in a:
    x=lcm(x,t)
x-=1
ans=0
for t in a:
    ans+=x%t
print(ans)
s=input()
n=len(s)
ans=0
for i in range(n):
  for j in range(i,n):
  bubun=s[i:j+1]
  flag=True
  for c in bubun:
    if(c not in ['A','G','C','T']):
      flag = False
  if(flag):
    ans = max(ans,len(bubun))
print(ans)


### FIXED CODE ###

s = input()
n = len(s) # 文字列の長さを取得しておく

res = 0 # 条件になければ0
for i in range(n): # Sの部分文字列を全探索するループ：重複を許す（i==jの時は1文字の部分文字列になる）が入替を許さないループ
    for j in range(i, n):
        sub = s[i: j+1] # i文字目からからj文字目までの部分文字列

        flg = True
        for c in sub: # Python的for文
            if(c not in ['A', 'G', 'C', 'T']): flg = False # こちらも、in はこういう時便利です

        if(flg): res = max(res, len(sub)) # ACGT文字列の長さnumの最大値を保持する

print(res)
n, m = map(int, input().split())
x = sorted([int(i) for i in input().split()])
diff_x = [x[i + 1] - x[i] for i in range(m - 1)]
max_diff = []
if m == 1:
    print(0)
else:
    for _ in range(n - 1):
        max_diff_i = diff_x.index(max(diff_x))
        max_diff.append(max_diff_i)
        diff_x[max_diff_i] = -10**6
    max_diff.sort()

    move = x[max_diff[0]] - x[0]
    for i in range(n - 2):
        move += x[max_diff[i + 1]] - x[max_diff[i] + 1]
    move += x[m - 1] - x[max_diff[n - 2] + 1]
    print(move)

### FIXED CODE ###

n, m = map(int, input().split())
x = sorted([int(i) for i in input().split()])
diff_x = [x[i + 1] - x[i] for i in range(m - 1)]
diff_x.sort(reverse=True)
if n >= m:
    print(0)
else:
    print((x[m - 1] - x[0]) - sum(diff_x[0:n - 1]))
import sys

N, K = map(int, input().split())
lst = list(map(int, input().split()))

lst_p = []
lst_m = []
for i in range(N):
    if lst[i] == 0:
        K -= 1
    if lst[i] > 0:
        lst_p += [lst[i]]
    elif lst[i] < 0:
        lst_m += [lst[i]]


p = 0
m = 0
x, y = 0, len(lst_m)-1
lastx = len(lst_p)
lasty = len(lst_m)
all_p = 10 ** 9
all_m = 10 ** 9
if K <= lastx:
    all_p = lst_p[K-1]
if K <= lasty:
    all_m = lst_m[lasty - K]

#print (all_p, all_m)
while True:
#    print (K)
    if K == 0: #K=残り回数が0のとき出力して終了
        print (min(2 * p + abs(m), p + 2 * abs(m), all_p, all_m))
        sys.exit()
    if x == lastx: #正側の数字を全て使い切った時
        m = lst_m[y]
        y -= 1
        K -= 1
    elif y == -1: #負側の数字を全て使い切った時
        p = lst_p[x]
        x += 1
        K -= 1
    elif lst_p[x] < abs(lst_m[y]): #負側のリスト絶対値のほうが大きい時-->正側の数字を採用
        p = lst_p[x]
        x += 1
        K -= 1
    else: #正側のリストのほうが大きい時-->負側の数字を採用
        m = lst_m[y]
        y -= 1
        K -= 1
     


### FIXED CODE ###

import sys

N, K = map(int, input().split())
lst = list(map(int, input().split()))

lst_p = []
lst_m = []
for i in range(N):
    if lst[i] == 0:
        K -= 1
    if lst[i] > 0:
        lst_p += [lst[i]]
    elif lst[i] < 0:
        lst_m += [lst[i]]


p = 0
m = 0
x, y = 0, len(lst_m)-1
lastx = len(lst_p)
lasty = len(lst_m)
#print (lastx, lasty)

def check(k):
    ans = 10 ** 9
    for j in range(0,k+1): #j: 正側の使う個数
#        print ('j, k-j', j, k-j)
        if j > lastx or k-j > lasty:
            pass
        else:
            if j == 0:
                p = 0
            else:
                p = lst_p[j-1]
            if k-j == 0:
                m = 0
            else:
                m = lst_m[lasty-(k-j)]
            ans = min(ans, 2 * p + abs(m), p + 2 * abs(m))
    return ans

print (check(K))
c=input().split
a=int(c)
b=int(c)
if a>b:
  print('a > b')
elif a<b:
   print('a < b')
else:
   print('a == b') 


### FIXED CODE ###

n=input().split()
a=int(n[0])
b=int(n[1])
if a > b:
    print("a > b")
elif a < b:
    print("a < b")
else:
    print("a == b")
A,B,H,M=map(float,input().split())
from math import sin, cos, pi

C = abs(30*H-5.5*M)
C = C if C <= 180 : 360-C
c =sqrt(A**2+B**2-2*A*B*cos(C*pi/180))
print(C)

### FIXED CODE ###

A,B,H,M=map(float,input().split())
from math import sin, cos, pi,sqrt

C = abs(30*H-5.5*M)
C = C if C <= 180 else 360-C
c =sqrt(A**2+B**2-2*A*B*cos(C*pi/180))
print(c)
code = len(set(list(str(input()))))
if code==4:
  print("Good")
else:
  print("Bad")

### FIXED CODE ###

s = raw_input()
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
  print('Bad')
else:
  print('Good')
n = int(input())
ans = n*(n+1)*(n+2)//6
for i in range(n-1):
  a, b = map(int, input.split())
  ans -= a*(n-b+1)
print(ans)


### FIXED CODE ###

n = int(input())
ans = n*(n+1)*(n+2)//6
for i in range(n-1):
  a, b = map(int, input().split())
  if b < a:
    a, b = b, a
  ans -= a*(n-b+1)
print(ans)
N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A)
diff = min([A[i+1] - A[i] for i in range(N-1)])
for a in [a for a in A if a >= K]:
    if (a - K) % diff == 0:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A)
if K in A:
    print('POSSIBLE')
else:
    temp = [A[i+1] - A[i] for i in range(N-1) if A[i+1] - A[i] > 0]
    diff = min(temp) if temp else -1
    if diff == -1:
        print('IMPOSSIBLE')
    else:
        for a in [a for a in A if a >= K]:
            if (a - K) % diff == 0:
                print('POSSIBLE')
                break
        else:
            print('IMPOSSIBLE')
print(input().swa

### FIXED CODE ###

inputa = input()
 
print(inputa.swapcase())
n,x=map(int,input().split())
d=[0]*(n+1)
ans=0
for i in range(n):
  d[i+1]=d[i]+int(input())
for i in range(n):
  if d[i]<=x:
    ans+=1
print(ans)


### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))
d=[0]*(n+1)
ans=0
for i in range(n):
  d[i+1]=d[i]+l[i]
for i in range(n+1):
  if d[i]<=x:
    ans+=1
print(ans)
a, b = input().split()
if (int(a)*int(b))%2 == 0:
    print ("Even")
else:
    print ("Odd")

### FIXED CODE ###

# 番号入力
s = int(input())
# 百の位
a = s//100
# 十の位
b = (s%100)//10
# 一の位
c = s%10
# 1の数を出力
n = a + b + c
print(n)
N = int(input())
p = [0]*N
for i in range(N):
    p[i] = int(inout())

ans = sum(p)-0.5*max(p)
print(ans)

### FIXED CODE ###

N = int(input())
p = [0]*N
for i in range(N):
    p[i] = int(input())

ans = sum(p)-0.5*max(p)
print(int(ans))
n= int(input())
h1=list(map(int,input().split()))
def fun(i):
    if i==n-1:
        best=0
    elif i==n-2:
        best=abs(h1[n-1]-h1[n-2])
    else:
        best=min(fun(i+1)+abs(h1[i+1]-h1[i]),fun(i+2)+abs(h1[i+2]-h1[i]))
    return best
print(fun(0))  
        

### FIXED CODE ###

n= int(input())
h1=list(map(int,input().split()))
dp=[-1 for i in range(n)]
def fun(i):
    if dp[i]!=-1:
        return dp[i]
    if i==n-1:
        best=0
    elif i==n-2:
        best=abs(h1[n-1]-h1[n-2])
    else:
        best=min(fun(i+1)+abs(h1[i+1]-h1[i]),fun(i+2)+abs(h1[i+2]-h1[i]))
    dp[i]=best
    return best
for k in range(n):
    fun(n-1-k)

print(fun(0))
s = range(n)
s = s.lower(k)
print(s)


### FIXED CODE ###

N, K = (int(i) for i in input().split())
S = list(input())

S[K - 1] = S[K - 1].lower()
print(''.join(S))
t1 = input()
t2 = t1[:4] + " " + t2[4:] + "\n"
print(t2)

### FIXED CODE ###

t1 = input()
t2 = t1[:4] + " " + t1[4:] 
print(t2)