# import sys
# sys.setrecursionlimit(10**5)
# def dfs(x):
# global n,a,b,c,s,d,md
# f=1
# for i in range(len(b)-1):
# if b[i]<c[i]:
# f=0
# break
# if f==1:
# if s>b[4]:
# s=b[4]
# md=[]
# for x in d:
# md.append(x)
# for i in range(x+1,n):
# for j in range(5):
# b[j]=b[j]+a[i][j]
# d.append(i+1)
# dfs(i)
# d.pop()
# for j in range(5):
# b[j]=b[j]-a[i][j]
# n=int(input())
# a=[]
# b=[0,0,0,0,0]
# c=list(map(int,input().split()))
# d=[]
# md=[]
# for i in range(n):
# t=list(map(int,input().split()))
# a.append(t)
# s=500**3
# dfs(-1)
# if s==500**3:
# print('-1')
# else:
# print(s)
# for x in md:
# print(x,end=' ')
# n,k=map(int,input().split())
# a=input()
# a=list(a)
# s=0
# for i in range(n):
# if a[i]=='H' or a[i]=='C':
# continue
# for j in range(i-k,i+k+1):
# if j<0 or j>=n:
# continue
# if a[j]=='H':
# a[j]='C'
# s=s+1
# break
# print(s)
# import sys
# input=sys.stdin.readline
# n,k=map(int,input().split())
# a=list(map(int,input().split()))
# b=[]
# for i in range(n):
# b.append([a[i],i])
# b=sorted(b,key=lambda x:x[0],reverse=True)
# c=[]
# for i in range(k):
# c.append(b[i])
# c=sorted(c,key=lambda x:x[1])
# s=0
# for i in range(k):
# s=s+a[c[i][1]]-i
# print(s)
# import sys
# input=sys.stdin.readline
# n=int(input())
# a=list(map(int,input().split()))
# s=0
# u=0
# ss=0
# for i in range(n):
# if a[i]%2==0:
# s=s+u
# else:
# u=u+1
# a.reverse()
# u=0
# for i in range(n):
# if a[i]%2==0:
# ss=ss+u
# else:
# u=u+1
# print(min(s,ss))
# def f(x):
# s=0
# y=list(str(x))
# for i in y:
# s=s+int(i)
# if x%s==0:
# return 1
# else:
# return 0
# n=int(input())
# s=0
# for i in range(1,n+1):
# if f(i)==1:
# s=s+1
# print(s)
# import sys
# input=sys.stdin.readline
# def f(x):
# s=0
# y=list(str(x))
# for i in y:
# if int(i)%3==0 and int(i)!=0:
# s=s+1
# return s
# n=int(input())
# s=0
# for i in range(1,n+1):
# s=s+f(i)
# print(s)