Harryxun/stf_run huggingface dataset:
#
# abc059 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
1 -3 1 0"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
3 -6 4 -5 7"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
-1 4 3 2 -5 4"""
        output = """8"""
        self.assertIO(input, output)


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

    ans = 0
    s = A[0]
    f = A[0] // abs(A[0])
    for i in range(1, N):
        a = A[i]
        if f == 1 and s+a >= 0:
            ans += abs(s+a) + 1
            s = -1
        elif f == -1 and s+a <= 0:
            ans += abs(s+a) + 1
            s = 1
        else:
            s += a
        f = s // abs(s)
    print(ans)


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


### FIXED CODE ###

#
# abc059 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
1 -3 1 0"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """5
3 -6 4 -5 7"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
-1 4 3 2 -5 4"""
        output = """8"""
        self.assertIO(input, output)


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

    # n = odd : plus
    ansa = 0
    sa = 0
    for i in range(N):
        sa += A[i]
        if i % 2 == 0:
            if sa >= 0:
                ansa += abs(sa) + 1
                sa = -1
        else:
            if sa <= 0:
                ansa += abs(sa) + 1
                sa = 1

    # n = even : plus
    ansb = 0
    sb = 0
    for i in range(N):
        sb += A[i]
        if i % 2 == 0:
            if sb <= 0:
                ansb += abs(sb) + 1
                sb = +1
        else:
            if sb >= 0:
                ansb += abs(sb) + 1
                sb = -1

    print(min(ansa, ansb))


if __name__ == "__main__":
    #unittest.main()
    resolve()
import re

S=input()
pat = r'[ATCG]+'
parts = re.findall(pat,S)
print 0 if len(parts)==0 else max([len(part) for part in parts])

### FIXED CODE ###

import re

S=input()
pat = r'[ATCG]+'
parts = re.findall(pat,S)
if len(parts)==0:
  print(0) 
else:
  print(max([len(part) for part in parts]))
num = int(input())

s = input()
t = input()
u =[]

for _ in range(num):
  u.append(s[_] + t[_])

ans = ''.join(u)

print(ans)

### FIXED CODE ###

num = int(input())

s, t = input().split()
u =[]

for _ in range(num):
  u.append(s[_] + t[_])

ans = ''.join(u)

print(ans)
N, K = map(int, input().split())
s3 =[]

s = list(input())

s1 = s


s2= s1[K]

s3 = s2.lower()

s1[K] = s3

print('' .join(s1))


### FIXED CODE ###

N, K = map(int, input().split())
s3 =[]

s = list(input())

s1 = s


s2= s1[K-1]

s3 = s2.lower()

s1[K-1] = s3

print('' .join(s1))
# ########## ------ Import ------- ##########

import sys
import math
from collections import Counter
from collections import deque as deq
from functools import lru_cache

# ########## ------ Define -------- #########

INT_MAX = float("inf")
INT_MIN = float("-inf")

# ########## ------ Input Functions ---- #########

input = sys.stdin.readline


def inp():
    return(int(input()))


def inlt():
    return(list(map(int, input().split())))


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


def invr():
    return(map(int, input().split()))


# ########## ------ Code ------- ##########
def go(i):
    if i == 0:
        dp[i] = 0
        return dp[i]
    if i == 1:
        dp[i] = abs(a[0] - a[i])
        return dp[i]

    if dp[i] != -1:
        return dp[i]

    dp[i] = min(abs(a[i] - a[i - 1]) + go(i - 1),
                abs(a[i] - a[i - 2]) + go(i - 2))
    return dp[i]


t = inp()
a = inlt()

if t == 1:
    print(0)
elif t == 2:
    print(abs(a[0] - a[1]))

else:

    dp[0] = 0
    dp[1] = abs(a[0] - a[1])
    for i in range(2, t):
        dp[i] = min(abs(a[i] - a[i - 1]) + dp[i - 1],
                    abs(a[i] - a[i - 2]) + dp[i - 2])

    print(dp[t - 1])


### FIXED CODE ###

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

dp = [0] * n
dp[1] = abs(arr[1] - arr[0])

for i in range(1, n - 1):
    dp[i + 1] = min(dp[i - 1] + abs(arr[i + 1] - arr[i - 1]), dp[i] + abs(arr[i + 1] - arr[i]))

print(dp[-1])
import functools
import math


def resolve():
	n,x=map(int,input().split())
	x_list=list(map(int,input().split()))
	x_list.append(x)
	a=[i-j for i in x_list for j in x_list if i!=j]
	print(functools.reduce(math.gcd,a))
resolve()

### FIXED CODE ###

import functools
import fractions

def resolve():
	n,x=map(int,input().split())
	x_list=list(map(int,input().split()))
	x_list.append(x)
	x_list.sort()
	a=[abs(x_list[i]-x_list[i+1]) for i in range(n)]
	print(functools.reduce(fractions.gcd,a))
resolve()
n = int(input())
nSum = 0
for i in range(n):
    cnt = 0
    for j in range(i + 1):
        if (i + 1) % (j + 1) == 0:
            cnt += 1
    if cnt == 8 and (i + 1) % 2 != 0:
        nSum += 1
        a.append(i + 1)

print(nSum)


### FIXED CODE ###

n = int(input())
nSum = 0
for i in range(n):
    cnt = 0
    for j in range(i + 1):
        if (i + 1) % (j + 1) == 0:
            cnt += 1
    if cnt == 8 and (i + 1) % 2 != 0:
        nSum += 1

print(nSum)
N = int(input())
S = input()
 
def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
 
        if Z[i] <= i:
            res = max(res, Z[i])
 
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
 
            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])
 
            k += 1
        i += k
        j -= k
    return res
 
ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)

### FIXED CODE ###

S = input()

if S == "Sunny":
    print("Cloudy")
elif S == "Cloudy":
    print("Rainy")
else:
    print("Sunny")
x=int(input())
mod=x%11
div=int(x/11)
if mod > 6:
    print(div*2+2)
elif: mod == 0:
    print(div*2)
else:
    print(div*2+1)

### FIXED CODE ###

x=int(input())
mod=x%11
div=int(x/11)
if mod > 6:
    print(div*2+2)
elif mod == 0:
    print(div*2)
else:
    print(div*2+1)
N = int(input())
F = []
for i in range(N):
    F_temp = list(map(int, input().split()))
    F.append(F_temp)
P = []
for i in range(N):
    P_temp = list(map(int, input().split()))
    P.append(P_temp)

ans = -1000000000

for i in range(1,1024):
    F0 = [0]*10
    i_temp = i
    for j in range(10):
        F0[j] = i_temp%2
        i_temp = int(i_temp/2)
    
    c = [0]*10
    for j in range(10):
        if F0[j] == 1:
            for k in range(N):
                c[k] += F[k][j]
    
    ans_temp = 0
    for j in range(N):
        ans_temp += P[j][c[j]]
    ans = max(ans, ans_temp)

print(ans)

### FIXED CODE ###

N = int(input())
F = []
for i in range(N):
    F_temp = list(map(int, input().split()))
    F.append(F_temp)
P = []
for i in range(N):
    P_temp = list(map(int, input().split()))
    P.append(P_temp)

ans = -1000000000

for i in range(1,1024):
    F0 = [0]*10
    i_temp = i
    for j in range(10):
        F0[j] = i_temp%2
        i_temp = int(i_temp/2)
    
    c = [0]*N
    for j in range(10):
        if F0[j] == 1:
            for k in range(N):
                c[k] += F[k][j]
    
    ans_temp = 0
    for j in range(N):
        ans_temp += P[j][c[j]]
    ans = max(ans, ans_temp)

print(ans)
N = int(input())
S = [str(input()) for _ in range(N)]

S = list(S)

for i in range(N):
    for j in range(N-1):
        if S[i] == S[j+1]:
            X = N - 1

print(X)

### FIXED CODE ###

import collections

num = int(input())
S = [str(input()) for _ in range(num)]

print(len(collections.Counter(S)))
def main(money):
  a  = money % 1000
  if a > 0:
    change = 1000 - a
 
  elif a = 0:
    change = 0
 
  print(int(change))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 20:25:04 2020

@author: KevinLU
"""
money = int(input())

a  = money % 1000
if a > 0:
    change = 1000 - a
else:
    change = 0
print(change)
S=input()
count=0
for i in range (len(S)):
    count+=int(S[i])
 
if int(S)%count==0:
    print ("Yes")
else:
    print ("No")

### FIXED CODE ###

S=input()
count=0
for i in range (len(S)):
    if S[i]=="+":
        count+=1
    else:
        count-=1
print(count)
a,b,k = map(int, input().split())
list = []
for i in range(a, b+1):
    list.append(i)
ans = []
for i in range(k):
    print(list[i])
for i in range(k):
    print(list[-k+i])

### FIXED CODE ###

a,b,k=map(int,input().split())
r=range(a,b+1)
for i in sorted(set(r[:k])|set(r[-k:])):print(i)
n=int(input())
a=[ 0 for _ in range (10000)]
for i in range(100):
  for J in range(100):
    for k in range(100):
      v=i**2+j**2+k**2+i*J+j*k+k*i
      if v<=10000:
        a[v]+=1
for m in range(n):
  print(a[m+1])

### FIXED CODE ###

n=int(input())
a=[0]*10001
for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      v=i**2+j**2+k**2+i*j+j*k+k*i
      if v<10001:
        a[v]+=1
for m in range(n):
  print(a[m+1])
def solve(s):
	if s[0]!='A':
    	return 'WA'
    if s[3:len(s)-1].count('C')!=1:
    	return 'WA'
    s=s.split('A').split('C')
    if not s.islower():
    	return 'WA'
    return 'AC'
  
s=input()
print(solve())
    	

### FIXED CODE ###

def solve(s):
    if s[0]!='A':
        return 'WA'
    if s[2:len(s)-1].count('C')!=1:
        return 'WA'
    s=str(s.split('A'))
    s=str(s.split('C'))
    if not s.islower():
        return 'WA'
    return 'AC'

s=input()
print(solve(s))
dict = {"A":"C", "C":"A", "G":"T", "T":"G"}
print(dict[b])


### FIXED CODE ###

b = input()
dict = {"A":"T", "T":"A", "C":"G", "G":"C"}
print(dict[b])
N = int(input())
A = int(input())

if N % 500 <= A:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
a, b = map(int, input().split(' '))
print(math.ceil((a+b)/2))
n,m = map(int,input().split())
#ac,wa列を作成（pi問題がACならac[i]がTRUE、AC,WAに問わずwa[i]はwaの数）
ac, wa=[False]*n,[0]*n
for i in range(m):
  p,s = input().split()
  p=int(p)
  if s=='AC':
    ac[p-1]=True
  elif (s=='WA') and (ac[p-1]==False):
    wa[p-1]+=1

penalty, clear=0,0
for i,tf in enumerate(ac): #iはインデックス、tfはac[i]
  if tf:
    penalty += wa[i] #piがACされているとき、ペナルティ値を増やす
    clear += 1
print(clear penalty)


### FIXED CODE ###

n,m = map(int,input().split())
#ac,wa列を作成（pi問題がACならac[i]がTRUE、AC,WAに問わずwa[i]はwaの数）
ac, wa=[False]*n,[0]*n
for i in range(m):
  p,s = input().split()
  p=int(p)
  if s=='AC':
    ac[p-1]=True
  elif (s=='WA') and (ac[p-1]==False):
    wa[p-1]+=1

penalty, clear=0,0
for i,tf in enumerate(ac): #iはインデックス、tfはac[i]
  if tf:
    penalty += wa[i] #piがACされているとき、ペナルティ値を増やす
    clear += 1
print(clear, penalty)
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10*6)

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in valid_items:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=input().strip(),list()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		value = list()
		for _ in range(H):
			value.append(list(x for x in input().strip()))
		print(solve(value))
		line = input().strip()

if __name__=='__main__':
	main()

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
n = int(input())
ans = [0 for i in range(1001)]
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            if (x*(x+y+z) + y*(y+z) + z*z) <= n:
                ans[(x*(x+y+z) + y*(y+z) + z*z)-1] += 1
for i in range(n):
    print(ans[i])

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10001)]
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            if x*x + y*y + z*z + x*y + x*z + y*z <= 10000:
                ans[x*x + y*y + z*z + x*y + x*z + y*z] += 1
            else:
              break
for i in range(1,n+1):
    print(ans[i])
inp = input().split()
n = int(inp[0])
m = int(inp[1])
favorite = [] #　i番目の人が好きなものの集合のリスト
for i in range(n):
    tmp = []
    tmp_inp = input().split()
    k = int(tmp_inp[0])
    for i in range(k):
        tmp.append(int(tmp_inp[i+1]))
    hyou.append(set(tmp))


def intersect_set(list):  # 集合のリストを受け取って、それらの積集合を返す
    result = list[0]
    for i in range(len(list)-1):
        result = result.intersection(list[i+1])
    return result

print(len(intersect_set(hyou)))


### FIXED CODE ###

inp = input().split()
n = int(inp[0])
m = int(inp[1])
hyou = []
for i in range(n):
    tmp = []
    tmp_inp = input().split()
    k = int(tmp_inp[0])
    for i in range(k):
        tmp.append(int(tmp_inp[i+1]))
    hyou.append(set(tmp))


def intersect_set(list):
    result = list[0]
    for i in range(len(list)-1):
        result = result.intersection(list[i+1])
    return result

print(len(intersect_set(hyou)))
import numpy as np
H, W, M = map(int, input().split())
HW = []
A = np.zeros((H, W), dtype='int')

for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    HW.append((h, w))
    A[h, w] = 1

arr = A.sum(axis=0)
col_max = arr.max()
col_idx = np.where(arr == col_max)[0]

arr = A.sum(axis=1)
row_max = arr.max()
row_idx = np.where(arr == row_max)[0]

# print(A.sum(axis=0).argsort()[-1])
if len(col_idx) * len(row_idx) >= M:
    print(col_max + row_max)
    exit()

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if A[r, c] == 0:
            print(ans)
            exit()
print(ans - 1)


### FIXED CODE ###

import numpy as np
H, W, M = map(int, input().split())

C = [0] * W
R = [0] * H
S = set()
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h - 1, w - 1  # 0-indexed
    C[w] += 1
    R[h] += 1
    S.add((h, w))

col_max = max(C)
col_idx = [i for i in range(W) if C[i] == col_max]
row_max = max(R)
row_idx = [i for i in range(H) if R[i] == row_max]

ans = col_max + row_max
for r in row_idx:
    for c in col_idx:
        if not (r, c) in S:
            print(ans)
            exit()
print(ans - 1)
alphabet=[chr(i+97) for i in range(0,26)]
S=input()

#S=    "zyawvutsrqponmlkjihgfedcbx"
if S=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:

    for i in S:
        alphabet.remove(i)
    if alphabet:
        print(S+alphabet[0])
    else:
        motoS=S
        S=list(S)
        poplist=[]
        stringlist=[]
        while len(S)>=2:
            poplist.append(S.pop())
            for s in poplist:
                _S=S
                _S[-1]=s
                string=""
                for ss in _S:
                    string+=ss
                stringlist.append(string)
        stringlist.append(motoS)
stringlist.sort()
print(stringlist[stringlist.index(motoS)+1])


### FIXED CODE ###

alphabet=[chr(i+97) for i in range(0,26)]
S=input()
if S=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in S:
        alphabet.remove(i)
    if alphabet:
        print(S+alphabet[0])
    else:
        motoS=S
        S=list(S)
        poplist=[]
        stringlist=[]
        while len(S)>=2:
            poplist.append(S[-1])
            S.pop()
            for s in poplist:
                _S=[i for i in S]
                _S[-1]=s
                string=""
                for ss in _S:
                    string+=ss
                stringlist.append(string)
        stringlist.append(motoS)
        stringlist.sort()
        try:print(stringlist[stringlist.index(motoS)+1])
        except:print(stringlist[stringlist.index(motoS)])
c=input()
if c='a' or c='i' or c='u' or c='e' or c='o':
  print('vowel')
else:
  print('consonant')

### FIXED CODE ###

c=input()
if c=='a' or c=='i' or c=='u' or c=='e' or c=='o':
  print('vowel')
else:
  print('consonant')
S=input()
if S==ABC:
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

S=input()
if S==("ABC"):
  print("ARC")
elif S==("ARC"):
  print("ABC")
Copy
S = input()
T = input()
 
S_list = []
T_list = []
alpha = "abcdefghijklmnopqrstuvwxyz"
 
for i in alpha:
    SS = S.count(i)
    TT = T.count(i)
    if SS and TT> 0:
        S_list.append(SS)
        T_list.append(TT)
 
if sorted(S_list) != sorted(T_list):
    print('No')
else:
    print('Yes')

### FIXED CODE ###

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

max = max([a, b, c])
print(max * 10 + a + b + c - max)
INF =10001
N = int(input())
h = [int(i) for i in input().split()]
i = 2
dp = [INF for i in range(N)]
dp[0],dp[1] = 0,abs(h[1]-h[0])
 
while i<N:
    dp[i] = min(dp[i],dp[i-1]+abs(h[i] - h[i-1]))
    dp[i] = min(dp[i],dp[i-2]+abs(h[i] - h[i-2]))
    i+=1
    
print(dp[n-1])

### FIXED CODE ###

INF =10001
N = int(input())
h = [int(i) for i in input().split()]
i = 2
dp = [INF for i in range(N)]
dp[0],dp[1] = 0,abs(h[1]-h[0])

while not i==N:
    dp[i] = min(dp[i-2]+abs(h[i] - h[i-2]),dp[i-1]+abs(h[i] - h[i-1]))
    i+=1
    
print(dp[N-1])
n, k = list(map(int, input().split()))
# print(n, k)


min_result = n
flag = 0
dic = {}

z = n // k
zz = n //z
result = zz

while flag==0:
    result = abs(result - k) 
    print('result',result)
    print('min_result',min_result)
    if result <= min_result:
        min_result = result
        dic[result] = dic.get(result, 0) + 1

        if dic[result] > 1:
            flag=1
print(min_result)

### FIXED CODE ###

n, k = list(map(int, input().split()))
# print(n, k)


x = n % k
y = k - x

if x > y:
    print(y)
    
else:
    print(x)
N, M, X, Y = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
flg = 'War'
for i in range(X, Y+1):
	if max(X) < i and i <= min(Y):
		flg = 'No ' + flg
		break
print(flg)

### FIXED CODE ###

N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
flg = 'War'
for i in range(X+1, Y+1):
	if max(x) < i and i <= min(y):
		flg = 'No ' + flg
		break
print(flg)
n = input()
list = list(map(int, input().split()))

count = 0
can = True
while can:
  for i in range(0, n):
    a = list[i]
    if a % 2 == 0:
      list[i] = a / 2
    else:
      can = False
  if can == True:
    count += 1
print(count)

### FIXED CODE ###

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

count = 0
can = True
while can:
  for i in range(0, int(n)):
    a = list[i]
    if a % 2 == 0:
      list[i] = a / 2
    else:
      can = False
  if can == True:
    count += 1
print(count)
k, s = map(int, input().split())

ans = 0

for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            ans += 1

print(ans)

### FIXED CODE ###

s = input()

print(s.replace(",", " "))
import sys
input = sys.stdin.readline
N = int(input())
rbg = [0, 0, 0]
ans = 1
for a in [int(a) for a in input().strip().split()]:
    ans = (ans * rbg.count(a)) % (10 ** 9 + 7)
    rbg[rbg.index(a)] += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
rbg = [0, 0, 0]
ans = 1
A = [int(a) for a in input().strip().split()]
for a in A:
    if rbg.count(a) == 0:
        print(0)
        exit()
    ans = (ans * rbg.count(a)) % (10 ** 9 + 7)
    rbg[rbg.index(a)] += 1

print(ans)
import numpy as np

def generate():
    newGen = np.zeros(n)
    for p in range(pop):
        gen = np.random.rand(n)
        for i in range(n):
            if gen[i] > 0.5:
                gen[i] = 1
            else:
                gen[i] = 0
        newGen = np.vstack([newGen,gen])
    newGen = np.vsplit(newGen,[1])[1]
    return newGen

def evaluate(gen):
    sum = np.zeros(pop)
    for p in range(pop):
        for i in range(n):
            sum[p] += v[i][1] * gen[p][i]
    sum = sum.reshape(pop, 1)
    gen = np.hstack([gen, sum])
    return gen

def best(gen):
    best0 = gen[0]
    for p in range(1,pop):
        if best0[-1] < gen[p][-1]:
            best0 = gen[p]
    return best0

def select(b,p):
    parents = np.zeros(b.shape[1])
    for i in range(p):
        p1 = b[np.random.randint(0, b.shape[0] - 1)]
        p2 = b[np.random.randint(0, b.shape[0] - 1)]
        if p1[-1] < p2[-1]:
            parents = np.vstack([parents, p2])
        else:
            parents = np.vstack([parents, p1])
    return np.vsplit(parents,[1])[1]

def crossover(parents):
    parents = np.hsplit(parents, [-1])[0]
    newGen = np.zeros(parents.shape[1])
    for i in range(parents.shape[0] / 2):
        l = np.random.randint(1, parents.shape[1] - 1)
        p1_0, p1_1 = np.hsplit(parents[i * 2], [l])
        p2_0, p2_1 = np.hsplit(parents[i * 2 + 1], [l])
        c1 = np.hstack([p1_0, p2_1])
        c2 = np.hstack([p1_1, p2_0])
        newGen = np.vstack([newGen, c1])
        newGen = np.vstack([newGen, c2])
    return np.vsplit(newGen, [1])[1]

def mutation(newGen):
    for p in range(pop):
        w_sum = 0
        for i in range(n):
            w_sum += newGen[p][i] * v[i][0]
        if w_sum > w:
            ran = np.random.permutation(np.arange(n))
            while(w_sum > w):
                ran, q = np.hsplit(ran,[-1])
                if newGen[p][q] == 1:
                    w_sum -= newGen[p][q] * v[q][0]
                    newGen[p][q] = 0
    return newGen


pop = 10
n, w = map(int,raw_input().split())
v = []
N = 500
for i in range(n):
    v.append(map(int,raw_input().split()))

eval = evaluate(generate())
c = mutation(crossover(select(eval,pop)))
eval = evaluate(c)
be = best(eval)
for i in range(N):
    c = mutation(crossover(select(eval,pop)))
    eval = evaluate(c)
    if be[-1] < best(eval)[-1]:
        be = best(eval)
print int(be[-1])

### FIXED CODE ###

a,b,c = raw_input().split()

if a[-1] == b[0] and b[-1] == c[0]:
    print("YES")
else:
    print("NO")
# A = [list(map(int, input().split())) for _ in range(3)]
# X = int(input())
# B = [int(input()) for _ in range(n)]
# A = list(map(int, input().split()))
k, n = map(int, input().split())
A = list(map(int, input().split()))
A.append(A[0]+k)
diff = 0
for i in range(n):
    diff = A[i+1]-A[i]
print(k-max(diff))


### FIXED CODE ###

# A = [list(map(int, input().split())) for _ in range(3)]
# X = int(input())
# B = [int(input()) for _ in range(n)]
# A = list(map(int, input().split()))
k, n = map(int, input().split())
A = list(map(int, input().split()))
diff = []
for i in range(n-1):
    diff.append(A[i+1]-A[i])
diff.append((k-max(A))+min(A))
print(k-max(diff))