# arr = []
# cnt = 10000
# check = []
#
# def search(a, n):
# global arr
# global check
# # print('>>>', a, n)
# for i in range(n):
# #print('vv', a, i)
# if arr[a][i] == 1 and check[i] != 1:
# check[i] = 1
# arr[a][i] = arr[i][a] = 0
# search(i,n)
# arr[a][i] = arr[i][a] = 1
# return
#
# def solution(n, wires):
# answer = -1
# global arr
# global check
# global cnt
# check = [0] * n
# for i in range(n):
# c = [0]*n
# arr.append(c)
#
# for i in range(len(wires)):
# arr[wires[i][0]-1][wires[i][1]-1] = arr[wires[i][1]-1][wires[i][0]-1] = 1
# #print(arr)
# for i in range(n):
# for j in range(n):
# #print(i, j)
# if arr[i][j] == 1:
# #print('x')
# arr[i][j] = arr[j][i] = 0
# check[0] = 1
# search(0, n)
# arr[i][j] = arr[j][i] = 1
# #print(check)
# u = sum(check)
# if u > n // 2:
# if cnt > u - (n - u):
# cnt = u - (n - u)
# else:
# if cnt > (n - u) - u:
# cnt = (n - u) - u
# check = [0] * n
#
# answer = cnt
# return answer
#
# z = 9
# h = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
# print(solution(z, h))
# import math
# ppp = []
# check = []
# cnt = 0
# ll = 0
# ans = []
# def prime(a):
# flag = 0
# if a == 0 or a == 1:
# return False
# for i in range(2, int(math.sqrt(a))+1):
# if a%i == 0:
# flag = 1
# break
# if flag == 1:
# return False
# return True
#
# def num(n,lp, le):
# #print('v', n, le)
# global cnt
# global ll
# global ppp
# if le == 1 :
# if prime(n):
# #print('rr', n)
# for i in range(len(ppp)):
# if ppp[i] == n:
# return
# ppp.append(n)
# cnt += 1
# else:
# for i in range(ll):
# if check[i] != 1:
# check[i] = 1
# #print('len 222', lp-le+1)
# num(n+ (ans[i] (10*(lp-le+1))),lp, le-1)
# check[i] = 0
#
# def solution(numbers):
# global cnt
# global ll
# global check
# answer = 0
# global ans
# ll = len(numbers)
# for i in range(ll):
# ans.append(int(numbers[i]))
# #print(ans)
# check = [0] * (ll+1)
# for i in range(1, ll+1):
# for j in range(ll):
# check[j] = 1
# num(int(numbers[j]), i, i)
# check[j] = 0
# answer = cnt
# return answer
#
# a = "123"
# print(solution(a))
# def solution(array, commands):
# answer = []
# ll = len(commands)
# for i in range(ll):
# sample = []
# for j in range(commands[i][0]-1, commands[i][1]):
# sample.append(array[j])
# sample.sort()
# answer.append(sample[commands[i][2]-1])
# return answer
#
# v = [1, 5, 2, 6, 3, 7, 4]
# c = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
# print(solution(v,c))