Harryxun/stf_run huggingface dataset:
debug = 0
"""
N: state num
M: city num
"""


if debug:
    N = 2
    m = 10
else:
    (N, M) = list(map(int, input().split()))

if debug:
    p_y_list = [
        [1, 30]
        ,[1, 20]
        ,[1, 10]
        ,[1, 3]
        ,[2, 63]
        ,[2, 33]
        ,[2, 23]
        ,[3, 21]
        ,[3, 7]
    ]

city_id_list = []
for num, z in enumerate(range(M)):
# for num, (P, Y) in enumerate(p_y_list):
    
    if not debug:
        (P, Y) = list(map(int, input().split()))

    city_id_list.append([Y, P, num])
    
city_id_list = sorted( city_id_list, key= lambda x: x[0])

state_cnt = {}
tmp_list = []
for (Y, P, num) in city_id_list:
    
    if P not in state_cnt.keys():
        state_cnt[P] = 1
    elif P in state_cnt.keys():
        state_cnt[P] += 1
        
    tmp_id = str(P).zfill(6) + str(state_cnt[P]).zfill(6)
    
    tmp_list.append([num, tmp_id])
    
for cid in sorted(tmp_list, key=lambda x: x[0]):
    print(cid[1])

### FIXED CODE ###

N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))

if N>=M:
    print(0)
else: 
    dist = [b-a for a, b  in zip(X, X[1:])]
    dist.sort()
    print(sum(dist[:M-N]))
N=int(input())
L=[0 for _ in range(N+1)]
L[0]=2
L[1]=1
for i in range(2,N+1):
  L[i]=L[i-1]+L[i-2]
print(L[N+1])

### FIXED CODE ###

N=int(input())
L=[0 for _ in range(N+1)]
L[0]=2
L[1]=1
for i in range(2,N+1):
  L[i]=L[i-1]+L[i-2]
print(L[N])
N = int(input())
a_list = list(map(int, input().split()))

for i in range(N-2):
    if a_list[i] <0 and a_list[i+1] < 0:
       a_list[i] *= -1
       a_list[i+1] *= -1

for i in range(N-2):
    if a_list[i] + a_list[i+1] < 0:
       a_list[i] *= -1
       a_list[i+1] *= -1

ans = sum(a_list)

min_list = []
for i in range(N):
    if a_list[i] < 0:
        min_list.append(a_list[i])

if len(min_list) % 2 == 0:
    abc = sum(min_list)
    abc *= -1
    print(ans + 2*abc)

if len(min_list) % 2 == 1 and len(min_list) !=1 :
    abc.sort()
    min_list = min_list[:-1]
    abc = sum(min_list)
    abc *= -1
    print(ans + 2*abc)

### FIXED CODE ###

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

for i in range(N-1):
    if a_list[i] <0 and a_list[i+1] < 0:
       a_list[i] *= -1
       a_list[i+1] *= -1

counter = 0
min_list = []
for i in range(N):
    if a_list[i] < 0:
        counter += 1
        min_list.append(a_list[i])

if counter % 2 == 0:
    abc = sum(min_list)
    abc *= -1
    ans = sum(a_list)
    print(ans + 2*abc)

if counter % 2 == 1:
    for i in range(N):
        if a_list[i] < 0:
            a_list[i] *= -1
    min_mun = min(a_list)
    ans = sum(a_list) - 2*min_mun
    print(ans)
S = input()
T = input()
ans = 0
for i in S and j in T:
    if i == j:
        ans += 1
print(ans)

### FIXED CODE ###

S = input()
T = input()
ans = 0
for i, j in zip(S, T):
    if i == j:
        ans += 1
print(ans)
import bisect

n = int(input())
l = list(int(i) for i in input().split())
l = sorted(l, reverse=True)

cnt = 0

for i in range(n - 2):
    a = l[i]
    for j in range(i + 1, n-1):
        b = l[j]
        cnt += bisect.bisectright(l, a-b)-(j+1)

print(cnt)


### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l = sorted(list(int(i) for i in input().split()))

    cnt = 0

    for i in range(n - 2):
        a = l[i]
        for j in range(i + 1, n-1):
            b = l[j]
            cnt += bisect.bisect_left(l, a+b)-(j+1)

    print(cnt)


if __name__ == "__main__":
    main()
import sys

n = int(sys.stin.readline().strip())

dist = {}

for i in xrange(0, n):
    array = map(int, sys.stdin.readline().strip().split(" "))
    for (j, d) in enumerate(array):
        dist[(i, j)] = d

searched = []
length = 0

target = 0

while len(searched) != n:
    searched.append(target)
    min_len = 2001
    for v in searched:
        for i in xrange(0, n):
            if (i not in searched) and (min_len > dist[(v, i)]) and (dist[(v, i)] != -1):
                min_len = dist[(v, i)]
                target = i
    length += min_len

print str(length)
                

### FIXED CODE ###

import sys

n = int(sys.stdin.readline().strip())

dist = {}

for i in xrange(0, n):
    array = map(int, sys.stdin.readline().strip().split(" "))
    for (j, d) in enumerate(array):
        dist[(i, j)] = d

searched = []
length = 0

target = 0

while len(searched) != n:
    searched.append(target)
    min_len = 2001
    for v in searched:
        for i in xrange(0, n):
            if (i not in searched) and (min_len > dist[(v, i)]) and (dist[(v, i)] != -1):
                min_len = dist[(v, i)]
                target = i
    if min_len != 2001:
        length += min_len

print str(length)
a,b=map(int,input().split())
cnt = 1
b -= a
if b == 1:
  print('0')
while True:
  if b > 0:
  	b -= (a - 1)
    cnt += 1
  else:
    print(cnt)
    break


### FIXED CODE ###

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

if b == 1:
  print('0')
else:
  cnt = 1
  b -= a
  while True:
    if b > 0:
      b -= (a - 1)
      cnt += 1
    else:
      print(cnt)
      break
MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 100

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

def nCr(n, r):
    return (fac[n] * modInverse[fac[r]] % MOD * modInverse[fac[n - r]] % MOD) % MOD

def modularInverse(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[MOD % i] * (MOD - MOD // i) % MOD
    return dp

fac = [1, 1]
for i in range(2, MAX + 1):
    fac.append((fac[-1] * i) % MOD)
modInverse = modularInverse(MAX)

ret = 0
for i in range(n - k + 2):
    for j in range(i + k - 1, n):
        diff = a[j] - a[i]
        between = max(0, j - i - 1)
        choose = max(0, k - 2)
        ret += (nCr(between, choose) * diff) % MOD
        ret %= MOD
print(ret)

### FIXED CODE ###

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

factorialNumInverse = [None] * (n + 1)
naturalNumInverse = [None] * (n + 1)
fact = [None] * (n + 1)

def inverseofNumber():
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, n + 1):
        naturalNumInverse[i] = (naturalNumInverse[MOD % i] * (MOD - MOD // i) % MOD)

def inverseofFactorial():
    factorialNumInverse[0] = factorialNumInverse[1] = 1
    for i in range(2, n + 1):
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % MOD

def factorial():
    fact[0] = 1
    for i in range(1, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

inverseofNumber()
inverseofFactorial()
factorial()

def nCk(n, k):
    ans = ((fact[n] * factorialNumInverse[k]) % MOD * factorialNumInverse[n - k]) % MOD
    return ans

def calcSum(a):
    ret = 0
    for i in range(k - 1, n):
        ret += (nCk(i, k - 1) * a[i]) % MOD
        ret %= MOD
    return ret

print((calcSum(a) - calcSum(a[::-1])) % MOD)
N=int(input())
S=input()
w=ans=9**9

for i in range(N):
    e=S[:i].count("W")
    w=S[i:].count("E")
    ans=min(ans,e+w)
    if w=0:break
print(ans)


### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
a,b = map(lambda x : int(x), input().split())
print(max(a - b * 2),0)

### FIXED CODE ###

a,b=map(lambda x:int(x),input().split())
print(max([0,a-b*2]))
import math
h = int(input())
l = math.floor(math.log2(h))
print(2**l * 2 -1)

### FIXED CODE ###

import math
h = int(input())
l = math.floor(math.log(h, 2))
print(2**l * 2 -1)
n = int(input())
a = list(map(int, input().split()))
aset = set(a)

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset):
  if a1 == 0:
    if a.count(a1) * 3 == N:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 = a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

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

if len(aset) == 1:
  if all(i == 0 for i in a):
    print("Yes")
  else:
    print("No")
elif len(aset) == 2:
  a1, a2 = sorted(aset)
  if a1 == 0:
    if a.count(a1) * 3 == n:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
elif len(aset) == 3:
  a1, a2, a3 = aset
  if a.count(a1) == a.count(a2) == a.count(a3):
    if a1 ^ a2 == a3:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")
MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

def dfs(pos: int, par: int):
    # posが白の時 -> 子はなんでも良い
    # posが黒の時 -> 子は全て白
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  # [白, 黒]

print(sum(dfs(0, -1)))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**6)

MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

def dfs(pos: int, par: int):
    # posが白の時 -> 子はなんでも良い
    # posが黒の時 -> 子は全て白
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  # [白, 黒]

print(sum(dfs(0, 0))%MOD)
n, k = map(int, input().split())

a = list(map(int, input().split()))
a_pos = list(sorted(filter(lambda x: x > 0, a), reverse=True))
a_neg = list(sorted(filter(lambda x: x < 0, a)))

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[0] * a_pos[1] > a_neg[0] * a_neg[1]:
        ans *= a_pos.pop(0)
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[0] * a_neg[1]:
        ans *= a_neg.pop(0) * a_neg.pop(0)
        k -= 2
    ans %= mod

print(ans)

### FIXED CODE ###

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

a = list(map(int, input().split()))
a_pos = sorted([i for i in a if i >= 0])
a_neg = sorted([i for i in a if i < 0], reverse=True)

mod = 10 ** 9 + 7
ans = 1

if len(a_pos) == 0 and k % 2:
    for i in a_neg[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

while k > 0:
    if k == 1 or len(a_neg) <= 1:
        if len(a_pos) == 0:
            ans *= a_neg.pop()
        elif len(a_pos) > 0:
            ans *= a_pos.pop()
        k -= 1
    elif len(a_pos) <= 1:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    
    elif a_pos[-1] * a_pos[-2] > a_neg[-1] * a_neg[-2]:
        ans *= a_pos.pop()
        k -= 1
    elif a_pos[0] * a_pos[1] <= a_neg[-1] * a_neg[-2]:
        ans *= a_neg.pop() * a_neg.pop()
        k -= 2
    ans %= mod

else:
    print(ans)
import numpy as np

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

for i in range(K, N+1):
    sum_prod = np.prod(A[i-K:i])
    if i > K:
        if sum_prod > tmp_sum_prod:
            print('Yes')
        else:
            print('No')
    tmp_sum_prod = sum_prod


### FIXED CODE ###

import functools
import operator

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

# prod = functools.partial(functools.reduce, operator.mul)
# tmp_sum_prod = prod(A[:K])
for i in range(K, N):
    sum_prod = (A[i]/A[i-K])
    if sum_prod > 1.0:
        print('Yes')
    else:
        print('No')
    tmp_sum_prod = sum_prod
# -*- coding: utf-8 -*-
N, M = map(int, input().split())


def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

if len(primes(M)) <= 1:
    print(1)
    exit()

mod = M % N
div = M // N
if mod == 0:
    print(M//N)
    exit()

# print(mod,div)
# for i in reversed(range(1,div)):
i = div - 1
while True:
    an = M - i*(N-1)
    if an % i == 0:
        print(i)
        exit()
    i -= 1

print(1)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
from collections import Counter

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

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


mod = M % N
div = M // N
if mod == 0:
    print(M//N)
    exit()

f = primes(M)

# 素数の場合などは１
if len(f) == 1:
    print(1)
    exit()

cnt = Counter(f)
ans_list = []

tmp_list = []
for k,v in cnt.items():
  tmp_list.append([i for i in range(v+1)])

# print(cnt)
# print(list(itertools.product(*tmp_list)))
for p in itertools.product(*tmp_list):
    tmp = 1
    for k,i in zip(cnt.keys(),p):
        tmp = tmp * (k ** i)

    if tmp > N:
        ans_list.append(M//tmp)

if len(ans_list) == 0:
    print(1)
else:
    print(max(ans_list))
N = int(input())

if N[0] == N[1] and N[1] == N[2]:
    print("Yes")
elif N[2] == N[1] and N[3] == N[2]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()

if N[0] == N[1] and N[1] == N[2]:
    print("Yes")
elif N[2] == N[1] and N[3] == N[2]:
    print("Yes")
else:
    print("No")
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
opo = [1 for i in range(n)]
cl = opo
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = opo

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
n, *a = [*open(0)]

if n==1:
    print('Yes')
    exit()
    
a = [int(i) for i in "".join(a).replace(" ", "")]
for i, x in enumerate(a[:-1]):
    if x-1 > a[i+1]:
        print('No')
        exit()
    
print('Yes')


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
 
for i in reversed(range(1,n)):
    if h[i] < h[i-1]:
        h[i-1] -= 1
        if h[i] < h[i-1]:
            print("No")
            exit()
print("Yes")
N = int(input())
A = list(map(int, input().split()))

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if i == 0:
            if A[i] != A[i + 1]:
                Sum += 1
        elif i < N - 1:
            if A[i] != A[i + 1] and A[i] != A[i - 1]:
                Sum += 1
        
print(Sum)


### FIXED CODE ###

from collections import defaultdict

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

DP = [0] * (10 ** 6 + 1)

A.sort()
Sum = 0

d = defaultdict(int)
for key in A:
    d[key] += 1

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if d[A[i]] == 1:
            Sum += 1
print(Sum)
import(sys)
n=int(input())
a = list(map(int,input().split()))
b=0
while(True):
  for i in range(n):
    if(a[i]%2!=0):
      print(b)
      sys.exit()
    a[i]=a[i]//2
  b+=1
print(b)

### FIXED CODE ###

N=input()
a=list(map(int,input().split()))
i=0
count=-1
b=[]
c=True
while c:
    i=0
    count+=1
    while i<int(N):
        if a[i]%2!=0:
            c=False
            break
        else:
            a[i]=a[i]/2
            i+=1
print(int(count))
n, _, y = map(int, input().split())
a = list(map(int, input().split()))
a = [y] + a

memo = [[-1 for i in range(n + 1)] for j in range(2)]
def sol(i, turn):
    # ovaj drugi ima a[i]
    if memo[turn][i] != -1:
        return memo[turn][i]
    best = abs(a[i] - a[n])
    for j in range(i + 1, n):
        pot = sol(j, 1 - turn)
        if turn == 0:
            best = max(best, pot)
        else:
            best = min(best, pot)
    memo[turn][i] = best
    return best

print(sol(0, 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**4)
n, _, y = map(int, input().split())
a = list(map(int, input().split()))
a = [y] + a

memo = [[-1 for i in range(n + 1)] for j in range(2)]
def sol(i, turn):
    # ovaj drugi ima a[i]
    if memo[turn][i] != -1:
        return memo[turn][i]
    best = abs(a[i] - a[n])
    for j in range(i + 1, n):
        pot = sol(j, 1 - turn)
        if turn == 0:
            best = max(best, pot)
        else:
            best = min(best, pot)
    memo[turn][i] = best
    return best

print(sol(0, 0))
A = list(map(int,input.split()))
if sum(A) <= 21:
    print("win")
else:
    print("bust")
    

### FIXED CODE ###


A = list(map(int,input().split()))
if sum(A) <= 21:
    print("win")
else:
    print("bust")
import sys

ans=0
g=[]
input()
for s in sys.stdin:
    for a in s.split():
        for u in g:
            if a in u:
                s+=u
    g+=[s]


print(max(len(set(t.split())) for t in g))



### FIXED CODE ###

import sys

n,m=map(int,next(sys.stdin).split())
adj=[[] for _ in range(n)]
for _ in range(m):
    ln=next(sys.stdin)
    a,b=map(int,ln.split())
    a,b=a-1,b-1
    adj[a].append(b)
    adj[b].append(a)

ans=0
vis=[0]*n
for i in range(n):
    if vis[i]:
        continue
    vis[i]=1
    k=0
    stk=[i]
    while stk:
        u=stk.pop()
        k+=1
        for v in adj[u]:
            if vis[v]:
                continue
            vis[v]=1
            stk.append(v)
    ans=max(ans,k)

print(ans)
inputa = list(map(int, input().split()))
inputb = list(map(int, input().split()))
inputc = list(map(int, input().split()))

seta = set(inputb) & set(inputc)

countb = []
countc = []
result = 0
for i in seta:
  countb.append(inputb.count(i))
  countc.append(inputc.count(i))
for i in range(len(countb)):
  for j in range(i)
  result += countb[i] * countc[j]

print(result)

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
S = input().split()
T = np.array(input().split(), dtype = np.int32)
mod = 10 ** 9 + 7
dp = np.ones(M + 1, dtype = np.int64)
 
for s in S:
  dp[1:] = ((dp[:-1] * (T == int(s))).cumsum() + dp[1:]) % mod

print(dp[M])
S = input()
T = input()
for i in range(S):
    S = S[-1] + S[:-1]
    if S == T:
        print('Yes')
        exit()
print('No')

### FIXED CODE ###

S = input()
T = input()
for i in range(len(S)):
    S = S[-1] + S[:-1]
    if S == T:
        print('Yes')
        exit()
print('No')
#include <stdio.h>
#include <math.h>

int main(void){
	int n;
	double x1,y1,x2,y2,x3,y3,a,b,c,s,ss,sina,r,px,py;
	scanf("%d",&n);
	while (n--){
		scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3);
		a = sqrt(pow(x1-x2,2)+pow(y1-y2,2));
		b = sqrt(pow(x1-x3,2)+pow(y1-y3,2));
		c = sqrt(pow(x2-x3,2)+pow(y2-y3,2));
		s = (a+b+c)/2;
		ss = sqrt(s*(s-a)*(s-b)*(s-c));
		sina = 2*ss/b/c;
		r = a/sina/2;
		a = a*a; b = b*b; c = c*c;
		px = (a*(b+c-a)*x3 + b*(a+c-b)*x2+c*(a+b-c)*x1)/16/pow(ss,2);
		py = (a*(b+c-a)*y3 + b*(a+c-b)*y2+c*(a+b-c)*y1)/16/pow(ss,2);
		printf("%.3f %.3f %.3f\n", px, py, r);
	}
	return 0;
}

### FIXED CODE ###

import math
n = int(raw_input())
for i in range(n):
    x1, y1, x2, y2, x3, y3 = map(float, raw_input().split())
    a = math.sqrt((x1-x2)**2+(y1-y2)**2)
    b = math.sqrt((x1-x3)**2+(y1-y3)**2)
    c = math.sqrt((x2-x3)**2+(y2-y3)**2)
    s = (a+b+c)/2
    ss = math.sqrt(s*(s-a)*(s-b)*(s-c))
    sina = 2*ss/b/c
 
    r = a/sina/2

    a = a*a
    b = b*b
    c = c*c
    px = (a*(b+c-a)*x3 + b*(a+c-b)*x2+c*(a+b-c)*x1)/16/ss**2
    py =(a*(b+c-a)*y3 + b*(a+c-b)*y2+c*(a+b-c)*y1)/16/ss**2

    print "%.3f %.3f %.3f" % (px, py, r)
from collections import deque
N = int(input())
A = sorted(list(map(int, input().split())))

ans = 0
  
while True:
  d = A.pop(0)
  if A[0] == d:
    d = A.pop(0)
  else:
    A = list(reversed([ a for a in A[::-1] if a % d != 0]))
    ans += 1
  if A:
    True
  else:
    break
  
print(ans)

### FIXED CODE ###

from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    if count[a] > 1:
      continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
print(main(np.array(A, np.int32)))
n = int(input())
list = [int(i) for i in input().split()]

n_max = max(list)
n_min = min(list)

print(n_max - n_min)

### FIXED CODE ###

n = int(input())
mod = n%2
if mod==0:
    dst = n
else:
    dst = n*2

print(dst)
import math
a,b,c = map(int,(input().split()))



left = 4 * a * b
d = c -a -b
right =d * d

if d < 0:
    print("No")
elif left < right 
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

left = 4 * a * b
d = c -a -b
right =d * d

if d < 0:
    print("No")
elif left < right:
    print("Yes")
else:
    print("No")
i = 0
while input() != 0:
    i += 1
    print('Case ',i,': ',input(),sep='')



### FIXED CODE ###

i = 0
while True:
    x = int(input())
    i += 1
    if x == 0:
        break
    print("Case {}: {}".format(i, x))
a = int(input())
b = int(input())
h = int(input())

print(int((a+b)/2*h)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())

print(int((a+b)/2*h))