Harryxun/stf_run huggingface dataset:
import collections

n = int(raw_input())
p = map(int,raw_input().split(' '))
q = map(int,raw_input().split(' '))


factorial[0] = 1
for i in range(1,9):
	cumul *= i
	factorial[i] = cumul


def f(p):
	if len(p) == 1: return 0
	sp = sorted(p)
	for i,e in enumerate(sp):
		if e == p[0]:
			hm = i
			break 

	return i * factorial[len(p) -1] + f(p[1:])


print abs(f(p) - f(q))

### FIXED CODE ###

import collections

n = int(raw_input())
p = map(int,raw_input().split(' '))
q = map(int,raw_input().split(' '))

def factorial(n): return (n * factorial(n-1)) if n>0 else 1


def f(p,n):

	if len(p) == 1:
		return 0
	sp = sorted(p)
	for i,e in enumerate(sp):
		if e == p[0]:
			hm = i
			break 

	return i * factorial(len(p) -1) + f(p[1:],n)


print abs(f(p,n) - f(q,n))
a =int(input())
x =list(map(int, input().split()))
x.sort()
s=0
for i in reversed(range(0,a//3,1):
  s+=x[i+1]
print(s)


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()

print(sum(A[n:3*n:2]))
def solv():
    s = ''.join(sorted(input()))
    t = ''.join(reversed(sorted(input())))

    if(s<t):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    solv()

### FIXED CODE ###

import math

def solv():
    a, b = map(int, input().split())
    x = (a + b)/2
    if (math.floor(x * 10) % 10 >= 5):
        print(math.floor(x)+1)
    else:
        print(math.floor(x))

if __name__ == '__main__':
    solv()
s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
        elif s[i-1] =='P':
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)


print(s)

### FIXED CODE ###

s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and len(s) == 1:
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
        elif s[i-1] =='P':
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1):
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i <len(s)-1 and(s[i+1] == 'P' or s[i+1] == '?')):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)


print(s)
if input()='1':
    print(Hello World)
else:
    A=int(input())
    B=int(input())
    print(A+B)

### FIXED CODE ###

N = int(input())
if N==1:
    print('Hello World')
else:
    A=int(input())
    B=int(input())
    print(A + B)
candidate = []
# べき乗リストを更新する
for i in range(32):
    if i >= 1:
        for j in range(32):
            if i**j <= 1000:
                if j > 1:
                    if i**j not in candidate:
                        candidate.append(i**j)
            else:
                break

candidate = sorted(candidate)
x = int(input())
result = 1
for c in candidate[1:]:
    if x >= c:
        result = c
    else:
        break
print(result)

### FIXED CODE ###

a, b, c, d = [int(i) for i in input().split()]
# abの通信可能性判定
if abs(a - b) <= d:
    ab = True
else:
    ab = False
# bcの通信可能性判定
if abs(b - c) <= d:
    bc = True
else:
    bc = False
# acの通信可能性判定
if abs(a - c) <= d:
    ac = True
else:
    ac = False

if ac == True or (ab == True and bc == True):
    print("Yes")
else:
    print("No")
'''input
3
1 2 2
2 3 1
'''

N = int(input())

edges = [[] for i in range(N)]

for i in range(N-1):
	a, b, w = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	edges[a].append((b, w))
	edges[b].append((a, w))


color = [None]*N

color[0] = 0

def dfs(curr, prev):
	for i in edges[curr]:
		if i[0] == prev: continue

		if i[1] % 2 == 0: color[i[0]] = color[curr]
		else: color[i[0]] = 1 - color[curr]

		dfs(i[0], curr)

dfs(0, -1)

for i in color:
	print(i)

### FIXED CODE ###

'''input
3
1 2 2
2 3 1
'''
import sys
sys.setrecursionlimit(100100)
N = int(input())

edges = [[] for i in range(N)]

for i in range(N-1):
	a, b, w = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	edges[a].append((b, w))
	edges[b].append((a, w))


color = [None]*N

color[0] = 0

def dfs(curr, prev):
	for i in edges[curr]:
		if i[0] == prev: continue

		if i[1] % 2 == 0: color[i[0]] = color[curr]
		else: color[i[0]] = 1 - color[curr]

		dfs(i[0], curr)

dfs(0, -1)

for i in color:
	print(i)
S = input()
C = input()
cnt = 0

for i in range(3):
  if S[i] == C[i]
  cnt++
print(cnt)

### FIXED CODE ###

S = input()
C = input()
cnt = 0
 
for i in range(3):
  if S[i] == C[i]:
  	cnt += 1
print(cnt)
import itertools

don = [int(input()) for i in range(5)]

final_time = inf
for v in itertools.permutations(don):
  time = 0
  for j in v:
    while(time % 10 != 0):
      time += 1
    time += j
  final_time = min(final_time, time)
print(final_time)


### FIXED CODE ###

import itertools

don = [int(input()) for i in range(5)]

final_time = float('inf')
for v in itertools.permutations(don):
  time = 0
  for j in v:
    while(time % 10 != 0):
      time += 1
    time += j
  final_time = min(final_time, time)
print(final_time)
N = int(input())
c=list(map(int, input().split()))
c.sort()

count = 0
while count<len(c):
  for i,b in enumerate(c):
    if i == count:
      continue
      
    print(i,b)
    if b%c[count]==0:
      c.pop(i)
      print(c)
  count+=1

print(c)



    

### FIXED CODE ###

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

c.sort()
a = c[N-1]
list_c = [0]*(a+1)
for i in c:
  mal = 2
  b = i
  while i<=a:
    list_c[i]+=1
    i = b*mal
    mal+=1
count = 0
for i in c:
  if list_c[i]==1:
    count+=1
print(count)
import heapq

INF = float('inf')
n, k = map(int, input().split())
sushi = {}

for _ in range(n):
    t, d = map(int, input().split())
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)

for s in sushi.values():
    s.sort(reverse=True)

eat_counts = {s: 0 for s in sushi.keys()}

# まだ食べてないやつ
news = []
# リピート
repeats = []
# 食べた履歴
eats = []

# 各寿司の一番おいしいやつを heap へ
for name, deli_li in sushi.items():
    # (-おいしさ, name)
    heapq.heappush(news, (-deli_li[0], name))

sum_deli = 0
variety = 0

for _ in range(k):
    # おいしいやつから食べる
    if news and (not repeats or news[0] <= repeats[0]):
        deli, name = heapq.heappop(news)
        variety += 1
    else:
        deli, name = heapq.heappop(repeats)

    sum_deli += -deli
    eat_counts[name] += 1
    heapq.heappush(eats, (-deli, name))
    if eat_counts[name] < len(sushi[name]):
        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))

# 美味しいやつから順に食べた
# 種類増やしたらもっと得点上がるか確かめる
ans = sum_deli + variety ** 2
while True:
    if not news:
        break

    # 食べたやつポイント小さいやつから置き換えたい
    ate_min_deli, ate_min_name = heapq.heappop(eats)
    eat_counts[ate_min_name] -= 1
    if eat_counts[ate_min_name] <= 0:
        # これは種類減っちゃうからだめ
        continue

    sum_deli -= ate_min_deli

    deli, name = heapq.heappop(news)
    variety += 1
    sum_deli += -deli
    eat_counts[name] += 1

    ans = max(ans, sum_deli + variety ** 2)

print(ans)


### FIXED CODE ###

import heapq

INF = float('inf')
n, k = map(int, input().split())
sushi = {}

for _ in range(n):
    t, d = map(int, input().split())
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)

for s in sushi.values():
    s.sort(reverse=True)

eat_counts = {s: 0 for s in sushi.keys()}

# まだ食べてないやつ
news = []
# リピート
repeats = []
# 食べた履歴
eats = []

# 各寿司の一番おいしいやつを heap へ
for name, deli_li in sushi.items():
    # (-おいしさ, name)
    heapq.heappush(news, (-deli_li[0], name))

sum_deli = 0
variety = 0

for _ in range(k):
    # おいしいやつから食べる
    if news and (not repeats or news[0] <= repeats[0]):
        deli, name = heapq.heappop(news)
        variety += 1
    else:
        deli, name = heapq.heappop(repeats)

    sum_deli += -deli
    eat_counts[name] += 1
    heapq.heappush(eats, (-deli, name))
    if eat_counts[name] < len(sushi[name]):
        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))

# 美味しいやつから順に食べた
# 種類増やしたらもっと得点上がるか確かめる
ans = sum_deli + variety ** 2
while True:
    if not news or not eats:
        break

    # 食べたやつポイント小さいやつから置き換えたい
    ate_min_deli, ate_min_name = heapq.heappop(eats)
    eat_counts[ate_min_name] -= 1
    if eat_counts[ate_min_name] <= 0:
        # これは種類減っちゃうからだめ
        continue

    sum_deli -= ate_min_deli

    deli, name = heapq.heappop(news)
    variety += 1
    sum_deli += -deli
    eat_counts[name] += 1

    ans = max(ans, sum_deli + variety ** 2)

print(ans)
a,b,c=sorted(map(int, input().split())
print(a+c)

### FIXED CODE ###

a,b,c=sorted(map(int, input().split()))
print(c-a)
import fraction

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

a -= 1

lcm = c * d // fraction.gcd(c, d)

b_sum = b - (b // c) - (b // d) + (b // lcm)
a_sum = a - (a // c) - (a // d) + (a // lcm)

print(b_sum - a_sum)

### FIXED CODE ###

import fractions

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

a -= 1

lcm = c * d // fractions.gcd(c, d)

b_sum = b - (b // c) - (b // d) + (b // lcm)
a_sum = a - (a // c) - (a // d) + (a // lcm)

print(b_sum - a_sum)
s = input()
if s[-1] == 's':
  s.append('es')
else:
  s.append('s')
print(s)

### FIXED CODE ###

s = input()
if s[-1] == 's':
    s += 'es'
else:
    s += 's'
print(s)
c=str(input())
print(c+1)

### FIXED CODE ###

c=str(input())
if c == 'a' :
    print("b")
elif c == 'b' :
    print("c")
elif c == 'c' :
    print("d")
elif c == 'd' :
    print("e")
elif c == 'e' :
    print ("f")
elif c == 'f' :
    print("g")
elif c == 'g' :
    print("h")
elif c == 'h' :
    print("i")
elif c == 'i' :
    print("j")
elif c == 'j' :
    print("k")
elif c == 'k' :
    print("l")
elif c == 'l' :
    print("m")
elif c == 'm' :
    print("n")
elif c == 'n' :
    print("o")
elif c == 'o' :
    print("p")
elif c == 'p' :
    print("q")
elif c == 'q' :
    print("r")
elif c == 'r' :
    print("s")
elif c == 's' :
    print("t")
elif c == 't' :
    print("u")
elif c == 'u' :
    print("v")
elif c == 'v' :
    print("w")
elif c == 'w' :
    print("x")
elif c == 'x' :
    print("y")
elif c == 'y' :
    print("z")
Sold = list(map(str, input()))
Snew = set(S)
alph = set(list('abcdefghijklmnopqrstuvwxyz'))
if len(list(Snew-alph))==0:
  print('none')
else:
  print(sorted(list(Snew-alph))[0])


### FIXED CODE ###

S = list(map(str, input()))
S = set(S)
a = set(list('abcdefghijklmnopqrstuvwxyz'))
if len(list(a-S)) == 0:
  print('None')
else:
  print(sorted(list(a-S))[0])
def same_count(str_list):
    standard_str = min(str_list, key=lambda x: len(x))
    return [all([c in str_ for str_ in str_list]) for c in standard_str].count(True)

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

print(max([same_count([s[:i], s[i:]]) for i in range(1,n-1)]))

### FIXED CODE ###

def same_count(str_list):
    standard_str = min(str_list, key=lambda x: len(x))
    return [all([c in str_ for str_ in str_list]) for c in set(standard_str)].count(True)

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

print(max([same_count([s[:i+1], s[i+1:]]) for i in range(n)]+[0]))
def ans(p, x):
    a = 0
    for i in x:
        a += (i - p)**2
    return a

n = int(input())
x = list(map(int, input().split()))

p = sum(x)//n

print(min(ans(p), ans(p+1)))


### FIXED CODE ###

def ans(p, x):
    a = 0
    for i in x:
        a += (i - p)**2
    return a

n = int(input())
x = list(map(int, input().split()))

p = sum(x)//n

print(min(ans(p, x), ans(p+1, x)))
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      s = str(dp[i-k])
      m = int(str(dic[k])+s)
      dp[i] = max(dp[i], m)
print(dp[N])

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
L=[0,2,5,5,4,5,6,3,7,6]
dp=[0]+[-1]*n
for i in range(n+1):
  for a in A:
    if i+L[a]<=n:
      dp[i+L[a]]=max(dp[i+L[a]],dp[i]*10+a)
print(dp[n])
import numpy as np

N = int(input())
l = list(map(int,input().split()))
a = np.array(l)
count = 0

for i in range(len(a)):
    if a[i]%2 == 0:
        if a[i]%3 != 0 and a[i]%5 != 0:
          count += 1:
            

if count:
    print("DENIED")
else:
    print("APPROVED")

### FIXED CODE ###

import numpy as np
 
N = int(input())
l = list(map(int,input().split()))
a = np.array(l)
count = 0

for i in range(len(a)):
    if a[i]%2 == 0:
        if a[i]%3 != 0 and a[i]%5 != 0:
            count += 1

if count:
    print("DENIED")
else:
    print("APPROVED")
s,w = map(int,split.input())


if s<=w:
  print('unsafe')
else:
  print('safe')

### FIXED CODE ###

s,w = map(int,input().split())

if s<=w:
  print('unsafe')
else:
  print('safe')
n,s=map(int,input().split())
l=[0]
for i in s:
  x= -1 if i=="D" else 1
  l+=[l[-1]+x]
print(max(l))

### FIXED CODE ###

n,s=int(input()),str(input())
l=[0]
for i in s:
  x= -1 if i=="D" else 1
  l+=[l[-1]+x]
print(max(l))
N = int(input())
S = input()

v = [S[i:i+N//2] for i in range(0, len(S), 2)]

if v[0] == v[1]:
  print("Yes")
else:
  print("No")




### FIXED CODE ###

n = int(input())
s = [i for i in input()]

if n%2 == 1:
  print("No")
else:
  if s[:int(n/2)] == s[int(n/2):]:
    print("Yes")
  else:
    print("No")
from functools import reduce
from operator import mul
import heapq

mod = 10**9 + 7

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

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

if N == K:
    print(reduce(mul, A)%mod)

else:

    AP = []
    AM = []
    for i in A:
        if i < 0:
            AM.append(-abs(i)%mod)
        else:
            AP.append(i%mod)
            
    if len(AP) == 0 and K%2 != 0:
        AM.sort(reverse=True)
        AM = AM[:K]
        print(reduce(mul, AM)%mod)

    else:
        AP = list(map(lambda x: x*(-1), AP))
        heapq.heapify(AP)
        heapq.heapify(AM)
        
        ans = 1
        cnt = 0
        while True:
            if (K - cnt) == 1:
                ans *= AP[0]
                print(ans%mod)
                break
                
            if 2 <= len(AM):
                AP2 = heapq.heappop(AP)*(-1)
                AP1 = heapq.heappop(AP)*(-1)
                

            if 2 <= len(AP):
                AM1 = heapq.heappop(AM)
                AM2 = heapq.heappop(AM)

                
            if AP1*AP2 >= AM1*AM2:
                ans *= AP1*AP2
                cnt += 2
                
            else:
                ans *= AM1*AM2
                m += 2
                cnt += 2 
                    
            if 1 >= len(AP) and 2 <= len(AM):
                ans *= AM1*AM2
                cnt += 2 
            
            if 2 <= len(AP) and 1 >= len(AM):
                ans *= AP1*AP2
                cnt += 2
            
            if cnt == K:
                print(ans%mod)
                break


### FIXED CODE ###

from bisect import bisect_left,bisect_right
p=10**9+7
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
pi=1
ni=0
ans=1
i=0
while i<k-1:
  if a[ni]*a[ni+1]>a[-pi]*a[-pi-1]:
    ans=ans*a[ni]*a[ni+1]%p
    ni+=2
    i+=2
  else:
    ans=ans*a[-pi]%p
    pi+=1
    i+=1
if i==k-1:
  ans=ans*a[-pi]%p
if a[-1]<0 and k%2==1:
  ans=1
  for i in a[n-k:]:
    ans=ans*i%p
print(ans)
a,b,c,d,e,k = [int(input) for i in range(6)]
print('Yay!' if e-a <= k else ':(')

### FIXED CODE ###

I =[int(input())for i in range(6)]

if I[4] - I[0] > I[5] :
	print(":(")
else :
	print("Yay!")
from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
list_1 = list(map(int,input().split()))
list_2 = list(map(int,input().split()))
list_3 = list(map(int,input().split()))

#n,m = map(int,raw_input().split())
#list_a = []
#for i in range(M) 
list_a=list_1


for x in list_2:
    list_a.append(x)


for x in list_3:
    list_a.append(x)


N = int(input())
#list_b = [int(x) for x in input().split()]
#list_b = list(map(int,input().split()))


list_b=[]
for k in range(N):
    b=int(input())
    list_b.append(b)


list_c = [0,0,0,0,0,0,0,0,0]
for i in range(N):
    for j in range(9):
        if list_a[j] == list_b[i]:
            list_c[j] = 1

flag=0
if list_c[0]==1 and list_c[1]==1 and list_c[2]==1:
    flag=1
if list_c[3]==1 and list_c[4]==1 and list_c[5]==1:
    flag=1
if list_c[6]==1 and list_c[7]==1 and list_c[8]==1:
    flag=1
if list_c[0]==1 and list_c[3]==1 and list_c[6]==1:
    flag=1
if list_c[1]==1 and list_c[4]==1 and list_c[7]==1:
    flag=1
if list_c[2]==1 and list_c[5]==1 and list_c[8]==1:
    flag=1
if list_c[0]==1 and list_c[4]==1 and list_c[8]==1:
    flag=1
if list_c[2]==1 and list_c[4]==1 and list_c[6]==1:
    flag=1
    
if flag == 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())

if n % 2 ==0:
    print(int(n/2))
else:
    print(int((n+1)/2))
N = int(input())
a =  list(map(int,input().split(" ")))

free = 0
arr = [0] * 8

for i in a:
	limit = 400
	while (limit <= 3200):
		if i < limit:
			arr[(limit // 400)-1] +=  1
			break
		else:
			limit += 400

	if limit== 3600:
		free += 1

color =  0
for i in arr:
	if i > 0:
		color += 1


print(str(max(1,str(color))) + " " + str(min(color + free,8)))




### FIXED CODE ###

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

free = 0
arr = [0] * 8

for i in a:
	limit = 400
	while (limit <= 3200):
		if i < limit:
			arr[(limit // 400)-1] +=  1
			break
		else:
			limit += 400

	if limit== 3600:
		free += 1

color =  0
for i in arr:
	if i > 0:
		color += 1


print(str(max(1,color)) + " " + str(color + free))
N, Q = map(int, input().split())

tree = dict()
parent = [0] * (N+1)
for _ in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  if a in tree:
    tree[a].append(b)
  else:
    tree[a] = [b]

action = [0] * (N+1)
for _ in range(Q):
  p, x = map(int, input().split())
  action[p] += x

counter = [0] * (N+1)

def score(i):
  global counter
  counter[i] = counter[parent[i]] + action[i]
  if i in tree:
    for ch in tree[i]:
      score(ch)

score(1)

ans = ' '.join([str(c) for c in counter[1:]])
print(ans)

### FIXED CODE ###

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

def abc138_d():
    N, _ = map(int, readline().strip().split())
    input_data = [tuple(map(int, ln.strip().split())) for ln in readlines()]

    # 隣接リスト作成
    graph = [[] for _ in range(N+1)]
    for a, b in input_data[:N-1]:
        graph[a].append(b)
        graph[b].append(a)

    # クエリをもとにスコア加算　※頂点pだけに加算し、子へは加算しない
    val = [0] * (N+1)
    for p, x in input_data[N-1:]:
        val[p] += x

    # DFSで根元から順に足していく
    stack = [1]
    visited =set([1])
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if y in visited: continue
            stack.append(y)
            visited.add(y)
            val[y] += val[x]

    print(*val[1:], sep=' ')

abc138_d()
a,b,c,d = map(int,input().split())import math
warareru = b-a+1
x = warareru//c
y = warareru//d
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)
z = warareru//lcm(c,d)
print(warareru-(x+y-z))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
import math
#最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

A = (a-1)//c + (a-1)//d - (a-1)//lcm(c,d)
B = b//c + b//d -b//lcm(c,d)

print((b-B)-((a-1)-A))
N, M = map(int,input().split())
A = []
B = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        B.append(b)
    if b == N:
        A.appned(a)
for a in A:
    if a in B:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


### FIXED CODE ###

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
a = int(input())
b = int(input())

if a*b==15: print("*")
elif a+b==15: print("+")
else :print("x")

### FIXED CODE ###

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

if a*b == 15:
    print("*")
elif a+b == 15:
    print("+")
else:
    print("x")
N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y
if N < x + y + z:
	print(-1, -1, -1)
	exit()
checked = []
def find(nx, ny, nz):
	if nx + ny + nz > N:
		return
	if find(nx, ny, nz):
		return
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
	if nx > 0:
		find(nx - 1, ny + 2, nz)
	if ny > 0:
		find(nx, ny - 1, nz + 5)
	checked.append((nx, ny, nz))
find(x, y, z)
print(-1, -1, -1)

### FIXED CODE ###

N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y
if N < x + y + z:
	print(-1, -1, -1)
	exit()
d = N - x - y - z
for dx in range(min(d, x) + 1):
	nx = x - dx
	ny = y + 2 * dx
	nd = N - nx - ny - z
	dy = min(nd // 4, ny)
	ny = ny - dy
	nz = z + dy * 5
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
print(-1, -1, -1)
s=input()
length=len(s)-2
print(s[0]+length+s[-1])

### FIXED CODE ###

s=input()
length=len(s)-2
print(s[0]+str(length)+s[-1])