# =======同行输入的数据类型不同，先转为str字符串后再强转===========================================
#
# 4 2.54
# n,m=map( str, input().split())
# n=int(n)
# m=float(m)
# print(n," ",m)
# ============当行2个输入===========循环嵌套选择结构 ===========================
# 1058 奇数求和
# m,n=map(int,input().split(' '))
# s=0
# for i in range(m,n+1):
# if i%2 :
# s+=i
# print(s)
#
# =============================================================================
# =======================不限定次数的while循环结构 ===========================
# 角谷猜想
# n=(int)(input())
# while (True):
# if (n==1): break
# if (n%2) :
# print("%d*3+1=%d" % (n,n*3+1))
# n=n*3+1;
# else :
# print("%d/2=%d" % (n,n/2))
# n=n/2;
# print("End")
#============================ 递归： n的全排列 ===================================
# res = [0] * n # 保存结果
# flag = [False] * (n+1)
# def dfs(u):
# if u == n:
# for i in res:
# print(i, end=" ")
# print()
# return
# # 判断当前位置可以遍历哪些数
# for i in range(1, n+1):
# if flag[i] == False:
# res[u] = i
# flag[i] = True
# dfs(u + 1)
# res[u] = 0
# flag[i] = False
# n = int(input())
# dfs(0)
#########################################################################
# 普通数组排序
# t=[4,6,2,8,1,7]
# t.sort(reverse=True)
# print(t)
#########################################################################
# 结构体排序(只有一个排序规则)
# 案例 输入姓名 成绩 输出第k名的人的名字
# def cmp(x):
# return int(x[1])
# N, k = map(int, input().split())
# list=[ ]
# for i in range(N):
# item=input().split() #输入姓名和成绩
# list.append(item)
# #list.sort(key=cmp,reverse=False)
# list.sort(key=lambda x:int(x[1]) )
# print(list[k-1][0])
#################### 输出列宽控制 #####################################################
# 结构体排序(有多个排序规则共同作用)
# 案例:排序年月日
# from functools import cmp_to_key #导入cmp_to_key方法
# def mycmp(a,b):
# if a[2]>b[2]:
# return 1
# elif a[2]==b[2]:
# if a[0]>b[0]:
# return 1
# elif a[0]==b[0]:
# if a[1]>b[1]:
# return 1
# else:
# return -1
# else:
# return -1
# else:
# return -1
# list=[]
# n=int(input())
# for i in range(n):
# item=input()
# # a=item.split('/') #输入月/日/年
# a=[]
# a.append(int(item[0:2]))
# a.append(int(item[3:5]))
# a.append(int(item[6:]))
# list.append(a)
# # list.sort( key=cmp_to_key(mycmp) )
# list.sort(key=lambda x:(x[2],x[0],x[1]) )
# for i in list:
# print('%.2d/%.2d/%.4d' % (i[0],i[1],i[2]))
# print('工资%.2f'%(8.6675))
##################### 整行输入存入二维数组 map 定义 ####################################################
# H, W = map(int, input().split())
# G = [input() for i in range(H)] #整行输入 LRUD G是一个二维数组
# mp={"U":[-1,0] ,"D":[1,0] ,"L":[0,-1] ,"R":[0,1] }
# x,y=0,0
# for i in range(0,250001):
# dx=x+mp[ G[x][y] ][0]
# dy=y+mp[ G[x][y] ][1]
# if( dx<0 or dy<0 or dx==H or dy==W ):#试探下一步的位置
# print(x+1,y+1)
# exit()
# x=dx;y=dy
# print(-1)
# ================= 整行输入 一维数组============================================================
# t=(int)(input())
#
# for i in range(1,t+1) :
# u=(int)(input())
# a=list( map(str,input().split(' ')) )
# print(a)
# ================== 整行输入 map中的查找 ===========================================================
# mp={}
# d=list( map(str,input().split(' ')) )
# for i in d:
# if(mp.get(i)!=None):
# mp[i]=1
# else:
# mp[i]=mp[i]+1
# ===================list 的迭代循环 基于iter ===================================================
# n=(int)(input())
#
# f=[ 2,3,5]
# for i in range(1,n+1):
# mp[i]=1
#
# for x in iter(f):
# for i in range(1,n+1):
# if(i%x==0):
# mp[i]=-mp[i]
#============================= 双重循环 ================================================
# n=(int)(input())
# t=2*n-1
# for i in range(0,n):
# print(i,end="")
# for j in range(0,i):
# print(' ',end="")
# for j in range(0,t):
# print('*',end="")
# t=t-2
# print()
# ==============================elif===============================================
# n=(int)(input())
# if(n<=9999 and n>=1000):
# print("%d\n%d\n%d\n%d" %( n//1000,n%1000//100,n%100//10,n%10 ))
# elif(n>=10 and n<=99):
# print("%d" %( n%10 ))
# else:
# print("no")
# ======================函数定义 回文字符串判定 ===============================
# def hw(s):
# i=0
# j=len(s)-1
# while(i<=j):
# if(s[i]!=s[j]):
# return False
# i=i+1
# j=j-1
# return True
#
#
# #12 21 12 31
#
# mp={}
# d=list( map(str,input().split(' ')) )
# s=len(d)
# for i in range(s):
# for j in range(s):
# if(i!=j):
# e=d[i]+d[j]
# if(hw(e)==True ):
# mp[e]=1
#
# print(len(mp))
# =============================================================================
# ======= list 常见操作 ===============================================
# a=list(range(10))
# a[:2]=[5] #将0,1项替换成5
# a.pop(5)#删除5下标的元素6
# a.remove(5) #删除第一个5
# if 3 in [1,2,3,4]:
# print(True)
# m=[1,2,3,4,5,6,7,8,9]
# m.append('a')
# m.append('a')
# ===============map的常见操作==================================================
# a={ "hello":80 , "study":60,"good":99 }
# print ( list( a.values() ) )
# print ( list( a.keys() ) )
# a={ "hello":"你好" , "study":"学习" ,"good":"好的" }
# a.pop("study")
# print(a)
# print( a[ "hello" ] )
# a.clear()
# print(a)
# print(type(a))
# =============================================================================
# =============================================================================
#
# n=(1,3,2)
# print(type(n))
# ===========fib 数列 ==================================================================
# fib=[0,1,1]
#
# for i in range (3,21):
# fib.append( fib[i-1]+fib[i-2] )
#
# print(fib)
# =============================================================================
# a,b,c = input().split('/')
# a=int(a)
# month = ['','January','February','March','April','May','June','July','August','September','October','November','December']
# print( "%s %s,%s" % (month[a],c,b ) )
# =============================================================================
# ====================单数据输入=========================================================
# T1780 时间转换
# n=int(input()) # 单行输入
# print("%d:%d:%d" %(n/3600,(n/60)%60,n%60))
# =============================================================================
# =====================sqrt获取========================================================
# T1346 两点之间的距离
# =============================================================================
# import math
# a,b,c,d=map(float,input().split()) # 先将输入转化为map结构，逐个赋值
# print("%.4lf"%(math.sqrt((a-c)*(a-c)+(b-d)*(b-d))));
# =============================选择结构========================================
# T1602 工作时间
# =============================================================================
# a,b,c,d = map(int,input().split(' '))
# if(b>=d):
# y=d+60-b
# x=c-a-1
# else:
# y=d-b
# x=c-a
# print("%d %d" % (x,y))
#
# =============================================================================
# =======================选择结构 本行打印结束符号自定义 逻辑与 and ======
#
# # 1038 判断能否被3，5，7整除
# n=(int)(input())
# if(n%3==0):
# print("3 ",end='')
# if(n%5==0):
# print("5 ",end='')
# if(n%7==0):
# print("7 ",end='')
# if(n%3!=0 and n%5!=0 and n%7!=0):
# print("n")
# =======================循环结构 及 range ======
# 1050 求平均年龄
# n=(int)(input())
# s=0
# for i in range(0,n): # 第三个参数可以放1
# j=(int)(input())
# s+=j
# print("%.2lf" % (s/n))
# =============================================================================
# 数组列表定义及 循环迭代器对象 iter
# =============================================================================#
#f=[3,4,5,6,7,8,9]
#
# print( f[ 0 : -1 : 2 ] )
#
# list=[1,2,3,4]
# for i in range(0, len(list) ):
# print (list[i], end=" ")
# print()
#for x in iter(f):
# print (x, end=" ")
# =============================================================================
# ================================二维数组定义及循环嵌套 =========================
#
# 1135 矩阵加法
# =============================================================================
# N=110
# t=[[0]*N]*N #二维数组
# s=[[0]*N]*N
# n,m=map(int,input().split())
#
# for i in range(0,n):
# t[i]=list( map(int,input().split()) )
#
# for i in range(0,n):
# s[i]=list( map(int,input().split()) )
#
# for i in range(0,n):
# for j in range(0,m):
# s[i][j]=s[i][j]+t[i][j]
# print(s[i][j],end=' ')
# print()
# =======================常见字符串操作 =======================================
# =============================================================================
# # T1122 最长最短单词
#
# s=input()
# s=s.split()
# it=iter(s)
# m1,s1,m2,s2=0,'',999999,''
#
# for c in it:
# if(len(c)>m1):
# m1=len(c)
# s1=c
# if(len(c)<m2):
# m2=len(c)
# s2=c
# print(s1)
# print(s2)
# =============================================================================
#T1115 字符串判等
# =============================================================================
# s=input()
# t=input()
# s=s.replace(' ','')
# t=t.replace(' ','')
# s=s.upper()
# t=t.upper()
# if(s==t):
# print("YES")
# else:
# print("NO")
# =============================================================================
# =======================ASCII值的获取与转化 ======================================================
# T1111 简单密码
# str=input()
# itr=iter(str)
# for c in itr:
# if(c>='A' and c<='E'):
# print(chr(ord(c)+21),end='')
# elif(c>='F' and c<='Z'):
# print(chr(ord(c)-5),end='')
# else :
# print(c,end='')
# ==================字符串查找 find =====================================
#T1118 删除单词后缀
# =============================================================================
# s=input()
#
#
# if( s.find("er",-2)!=-1 ):
# s=s[:-2]
# print(s)
#
# =============================================================================
#########################################################################
# python中的集合
# =============================================================================
# x = set('runoob')
# y = set('googbe')
#
# print(x)
# print(y)
# print(x&y) #交集 两个集合中公共的部分
# print(x|y) #2集合中 的所有不重复的元素，合并在一起
# print(x-y) # x-y 在x中但不在y中的所有元素
# print(x^y) #补集:x-y | y-x
# =============================================================================
#########################################################################
# python中的类及属性创建
# class student:
# x = 0
# c = 0
# def f(stu):
# stu.x = 20
# stu.c = 'c'
# a= student()
# a.x = 3
# a.c = 'a'
贪心
双指针
前缀和
差分
优先队列 堆
DFS
BFS
最小生成树
并查集
