20231225

# def f(n):

# if n == 1 or n == 2:

# memo[n] = 1

# return 1

# if memo[n] != 0:

# return memo[n]

# memo[n] = f(n - 1) + f(n - 2)

# return memo[n]

#

#

# n = int(input())

# memo = [0] * (n+1)

# print(f(n))

import sys

limit_number = 2000000000

sys.setrecursionlimit(limit_number)

# def f(n, k):

# global me

# if n == 1:

# return 1

# if k == 1:

# me[k] = n

# return n

# if me[k] != 0:

# return me[k]

# if k % 2 == 0:

# me[k] = (f(n, k // 2) * f(n, k // 2)) % 1000000007

# return me[k]

# else:

# me[k] = (n f(n, k // 2) f(n, k // 2)) % 1000000007

# return me[k]

#

#

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

# me = [0] * (k + 1)

# print(f(n, k))

# import sys

# limit_number = 2000000

# sys.setrecursionlimit(limit_number)

#

#

# def f(b1, t1, p):

# b = b1

# t = t1

# global d

# print(d)

# while b < t:

# if d[b][0] <= d[p][0] <= d[t][0]:

# t = t - 1

# b = b + 1

# elif d[t][0] <= d[p][0] <= d[b][0]:

# tt = d[t]

# d[t] = d[b]

# d[b] = tt

# t = t - 1

# b = b + 1

# elif d[t][0] <= d[p][0]:

# b = b + 1

# else:

# t = t - 1

#

# for i in range(p + 1, t1 + 1, 1):

# if d[i][0] < d[p][0]:

# kk = d[i]

# d[i] = d[p]

# d[p] = kk

# break

# if b1 < b:

# if b == b1 + 1 and d[b1][0] < d[b][0]:

# u = 0

# else:

# f(b1, b, b1 - 1)

# if b1 < b - 1:

# if b == b1 + 2 and d[b1][0] < d[b][0]:

# u = 0

# else:

# f(b1, b - 1, b1 - 1)

# if t + 1 < t1:

# if t1 == t + 2 and d[t + 1][0] < d[t1][0]:

# u = 0

# else:

# f(t + 1, t1, t + 1)

# n = int(input())

# d = []

# for i in range(n):

# v = [i] * 2

# d.append(v)

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

# for i in range(n):

# d[i][0] = k[i]

#

# for i in range(1, n, 1):

# l = i

# for j in range(i - 1, -1, -1):

# if d[j] > d[l]:

# t = d[j]

# d[j] = d[l]

# d[l] = t

# l = j

#

# for i in range(n):

# for j in range(n):

# if d[j][1] == i:

# print(j, end=' ')

# n = int(input())

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

#

# if arr[0] + arr[1] >= 0:

# k = arr[0] + arr[1]

# else:

# k = - arr[0] - arr[1]

#

# a = arr[0]

# b = arr[1]

#

# for i in range(n):

# for j in range(i + 1, n):

# if k == 0:

# break

# s = arr[i] + arr[j]

# if s == k:

# continue

# elif s == 0:

# k = 0

# a = arr[i]

# b = arr[j]

# break

# elif s >= 0:

# if s < k:

# k = s

# a = arr[i]

# b = arr[j]

# else:

# continue

# elif s < 0:

# if -s < k:

# k = -s

# a = arr[i]

# b = arr[j]

# else:

# continue

# if k == 0:

# break

#

# if a > b:

# tt = a

# a = b

# b = tt

#

# print(a, b)

# import sys

# limit_number = 2000000

# sys.setrecursionlimit(limit_number)

#

#

# def f(b1, t1, p):

# b = b1

# t = t1

# global d

# while b < t:

# if d[b] <= d[p] <= d[t]:

# t = t - 1

# b = b + 1

# elif d[t] <= d[p] <= d[b]:

# tt = d[t]

# d[t] = d[b]

# d[b] = tt

# t = t - 1

# b = b + 1

# elif d[t] <= d[p]:

# b = b + 1

# else:

# t = t - 1

# if d[t] < d[p]:

# kk = d[p]

# d[p] = d[t]

# d[t] = kk

# else:

# for i in range(t - 1, p, -1):

# if d[i] < d[p]:

# kk = d[i]

# d[i] = d[p]

# d[p] = kk

# break

# if b1 < b - 1:

# if b == b1 + 2 and d[b1] < d[b - 1]:

# u = 0

# else:

# f(b1, b - 1, b1 - 1)

# if t + 1 < t1:

# if t1 == t + 2 and d[t + 1] < d[t1]:

# u = 0

# else:

# f(t + 1, t1, t + 1)

# if p + 1 < n and d[p + 1] < d[p]:

# qw = d[p]

# d[p] = d[p + 1]

# d[p + 1] = qw

#

#

# n = int(input())

# k = [0] * n

# d = list(map(int, input().split()))

# for i in range(n):

# k[i] = d[i]

#

# f(1, n - 1,0)

#

# for i in range(n):

# for j in range(n):

# if k[i] == d[j]:

# print(j, end=' ')