# import copy
#
#
# def f(n, arr):
# for i in range(n // 2 - 1, -1, -1):
# if arr[i] == n - 1:
# arr[i] = 0
# else:
# arr[i] += 1
# break
#
#
# def g(n, md, rd):
# m = []
# h = []
# su(m, 0, n // 2, h, md)
#
# r = []
# l = []
# su(r, 0, n // 2, l, rd)
#
# v = 0
# for i in range(len(m)):
# for j in range(len(r)):
# if m[i] > r[i]:
# v += 1
#
# return v
#
#
# def su(m, t, a, h, md):
# if t == a:
# s = 0
# for i in range(len(h)):
# s += md[i][h[i]]
# m.append(s)
# return
# for i in range(6):
# h1 = copy.deepcopy(h)
# h1.append(i)
# su(m, t + 1, a, h1, md)
#
#
# def solution(dice):
# answer = []
# n = len(dice)
# if n == 2:
# v = [0] * 2
# for i in range(6):
# for j in range(6):
# if dice[0][i] > dice[1][j]:
# v[0] += 1
# elif dice[0][i] < dice[1][j]:
# v[1] += 1
# for i in range(2):
# if max(v) == v[i]:
# answer.append(i + 1)
# break
#
# else:
# p = 0
# q = []
# arr = [0] * (n // 2 - 1)
# arr.append(-1)
# while min(arr) != n - 1:
# f(n, arr)
# check = 0
# for i in range(len(arr)):
# for j in range(i + 1, len(arr), 1):
# if arr[i] == arr[j]:
# check = 1
# break
# if check == 1:
# break
# if check == 1:
# continue
#
# md = []
# rd = []
# for i in range(n):
# if arr.count(i) == 1:
# md.append(dice[i])
# else:
# rd.append(dice[i])
#
# k = g(n, md, rd)
#
# # print(arr, k)
#
# if k > p:
# p = k
# q = copy.deepcopy(arr)
# print(p, q)
#
# for i in range(len(q)):
# answer.append(q[i] + 1)
# answer.sort()
#
# return answer
#
#
# d = []
# for i in range(8):
# v = list(map(int, input().split()))
# d.append(v)
# print(solution(d))
#
# '''
# 1 2 3 4 5 6
# 3 3 3 3 4 4
# 1 3 3 4 4 4
# 1 1 4 4 5 5
# 40 41 42 43 44 45
# 43 43 42 42 41 41
# 1 1 80 80 80 80 80
# 70 70 1 1 70 70
# '''
# import sys
# limit_number = 150000
# sys.setrecursionlimit(limit_number)
#
#
# memo = [0] * 20000000
#
#
# def f(n, tops):
# global memo
# top = tops[(n - 2) // 2]
# if memo[n] != 0:
# return memo[n]
# if n == 0:
# memo[n] = 0
# return memo[n]
# if n == 1:
# memo[n] = 1
# return memo[n]
# if n == 2:
# if top == 0:
# memo[n] = 2
# else:
# memo[n] = 3
# return memo[n]
# if n == 3:
# if top == 0:
# memo[n] = 3
# else:
# memo[n] = 4
# return memo[n]
#
# if top == 1 and n % 2 == 0:
# memo[n] = f(n - 1, tops) * 2
# else:
# memo[n] = f(n - 1, tops)
#
# memo[n] += f(n - 2, tops)
# return memo[n] % 10007
#
#
# def solution(n, tops):
# answer = f(2 * n + 1, tops) % 10007
# return answer
#
#
# a = int(input())
# t = [0] * a
# print(solution(a, t))