Q 4751 super long
some unsolved/wrong questions
# Q 4031
# numbers = list(map(int, input().split()))
# b = 0
# c = 0
# for i in range(7):
# a = numbers[i]
# if a % 2 == 1:
# if a > b:
# b = 0
# b += a
# if a % 2 == 0:
# if a > c:
# c = 0
# c += a
# print(b+c)
#
#
#
# Q 4036
# n = int(input())
# m = int(input())
# a = 0
# b = 0
# for i in range (1000001, 1, -1):
# c = i # a
# d = n - c #b
# if c - d == m:
# a = c
# b = d
# break
# print(a)
# print(b)
#
#
#
#
# Q 4041
# a = list(input())
# b = 0
# c = 0
# for i in range(len(a)):
# z = int(a[i])
# b += z 10 * i
# c += z
# print(b)
# print(c)
#
#
#
# Q 4501
# height = []
# for i in range(7):
# height.append(int(input()))
# height.sort()
# height.sort(reverse=True)
# a = height[0]
# b = height[1]
# print(a)
# print(b)
#
#
#
# Q 4506
# a, b = input().split()
# a = int(a)
# b = int(b)
# for i in range(1, 10001):
# if a % i == 0:
# if b % i == 0:
# c = 0
# c += i
# print(c)
# d = (a*b)//c
# print(d)
#
#
#
# Q 4051
# money = 0
# totaltime = 0
# for i in range (5):
# a, b = input().split()
# a = float(a)
# b = float(b)
# c = b-a
# time = c-1
# if time < 0:
# time = 0
# elif time > 4:
# time = 4
# totaltime += time
# money += (time/0.5)*5000
# if totaltime >= 15:
# money -= money*0.05
# elif totaltime <= 5:
# money += money*0.05
# print(int(money))
#
#
#
# Q4531
# numbers = []
# for i in range(5):
# numbers.append(int(input()))
# numbers.sort()
# d = numbers[2]
# c = 0
# for i in range(5):
# c += numbers[i]
# c = c // 5
# print (c)
# print (d)
#
#
#
# Q 4591
# numbers = []
# order = []
# for i in range(9):
# numbers.append(int(input()))
# order.extend(numbers)
# numbers.sort()
# print(numbers[8])
# print((order.index(numbers[8])) + 1)
#
#
#
# Q4056
# money = int(input())
# if money <= 500:
# money = money*0.7
# elif 500 < money <= 1500:
# money = 350 + ((money-500)*0.4)
# elif 1500 < money <= 4500:
# money = 750 + ((money-1500)*0.15)
# elif 4500 < money <= 10000:
# money = 1200 + ((money-4500)*0.05)
# elif money > 10000:
# money = 1475 + ((money-10000)*0.02)
# print(int(money//1))
#
#
#
# Q 4561
# numbers = list(map(int, input()))
# odds = []
# oddtotal = 0
# for i in range(7):
# z = numbers[i]
# if z % 2 == 1:
# odds.append(z)
# oddtotal += z
# odds.sort()
# if oddtotal == 0:
# print('-1')
# else:
# print(oddtotal)
# print(odds[0])
#
#
#
# Q4566
# m = int(input())
# n = int(input())
# allpossible = []
# prime = []
# for i in range(m,n+1):
# allpossible.append(i)
# allpossible.sort()
# for i in range(m, n+1):
# for j in range (m, n+1):
# if allpossible[i] % j != 0:
# if j != allpossible[i] and j != 1:
# prime.append(allpossible[i])
# prime.sort()
# total = 0
# for i in range(len(prime)):
# total += prime[i]
# print(total)
# print(prime[0])
#
#
#
# Q4571
# m = int(input())
# n = int(input())
# jegopsu = []
# for i in range(m, n+1):
# for j in range(m, n+1):
# if i / j == j:
# jegopsu.append(i)
# jegopsu.sort()
# z = 0
# for i in range(len(jegopsu)):
# z += int(jegopsu[i])
# print(z)
# print(jegopsu[0])
#
#
#
# Q4592
# n = int(input())
# for i in range(n):
# leftx = int(input())
# downy = int(input())
# rightx = leftx + 10
# upy = downy + 10
# for j in range(leftx, rightx):
# for k in range(downy, upy):
# # 어떻게 겹치는지, 어디의 자리를 차지하는지 알리는 방법을 모르겠다
#
#
#
# Q4626
# n = int(input())
# point = 0
# for i in range(n):
# if n[i+1] == 1:
# if n[i] == 0:
# point+=1
# elif n[i] == 1:
# #어떻게 연속문제 맞기를 표현해야할지 모르겠다
# for i in range(len(point)):
# z += int(point[i])
# print(z)
#
#
#
# Q4621
# n, m = map(int, input().split())
# yaksu = []
# for i in range(1,n+1):
# if n % i == 0:
# yaksu.append(i)
# yaksu.sort()
# if len(yaksu) < m:
# print('0')
# else:
# print(yaksu[m-1])
#
#
#
#
#
#
# Q4681
# numbers = input().split()
# gumjeung = 0
# for i in range(5):
# z = int(numbers[i])
# gumjeung += z*z
# print(gumjeung%10)
#
#
#
# Q4891
# rnhour, rnmin = map(int, input().split())
# addmin = int(input())
# min = rnmin + addmin
#
#
#
#
# if addmin > 59:
# addhour = addmin//60
# restmin = addmin%60
# if rnmin+restmin > 59:
# if rnhour + addhour == 23:
# print('0', rnmin+restmin-60)
# elif rnhour + addhour > 23:
# print(rnhour + addhour - 23, rnmin + restmin - 60)
# else:
# print(rnhour + addhour + 1, rnmin + restmin - 60)
# elif rnhour == 23:
# print(0 + addhour, rnmin + restmin)
# elif rnhour + addhour > 23:
# print(rnhour+addhour-24, rnmin+restmin)
# else:
# print(rnhour + addhour, rnmin + restmin)
#
# elif rnmin + addmin > 59:
# if rnhour == 23:
# print('0', min - 60)
# else:
# print(rnhour + 1, min - 60)
#
# else:
# print(rnhour, min)
#
#
#
# Q4746
# rnhour, rnmin, rnsec = map(int, input().split())
# addsec = int(input())
# totalrnsec = rnhour*3600 + rnmin*60 + rnsec
# addallsec = totalrnsec + addsec
# newhour = addallsec // 3600
# newmin = (addallsec - newhour*3600) // 60
# newsec = addallsec - newhour*3600 - newmin*60
# if newhour > 23:
# leftoverhour = newhour // 24
# print(newhour-24*leftoverhour, newmin, newsec)
# else:
# print(newhour, newmin, newsec)
#
#
#
# Q4651
# for i in range(1, 4):
# throw = list(map(int, input().split()))
# ones = throw.count(1)
# if ones == 3:
# print('A')
# elif ones == 2:
# print('B')
# elif ones == 1:
# print('C')
# elif ones == 0:
# print('D')
# elif ones == 4:
# print('E')
#
#
#
# #Q4891
# n = int(input())
# scores = list(map(int,input().split()))
# scores.sort()
# difference = scores[n-1] - scores[0]
# print(difference)
#
#
#
# Q4751 (wrong)
# n = int(input())
# wincountry = 0
# winnumber = 0
# winscore = 0
# secondcountry = 0
# secondnumber = 0
# secondscore = 0
# thirdcountry = 0
# thirdnumber = 0
# thirdscore = 0
# for i in range(n):
# country, number, score = map(int, input().split())
# if wincountry == secondcountry == country or wincountry == thirdcountry== country or secondcountry == thirdcountry== country or wincountry ==secondcountry == thirdcountry== country:
# if ????????????
# if score > winscore:
# winscore = 0
# winscore += score
# winnumber = 0
# winnumber += number
# wincountry = 0
# wincountry += country
# elif score > secondscore:
# secondscore = 0
# secondscore += score
# secondnumber = 0
# secondnumber += number
# secondcountry = 0
# secondcountry += country
# elif score > thirdscore:
# thirdscore = 0
# thirdscore += score
# thirdnumber = 0
# thirdnumber += number
# thirdcountry = 0
# thirdcountry += country
#
#
#
# #Q 4751
# n = int(input())
# everything = [] # ALL VALUES OF ONE ROW = LIST, EVERYTHING = LIST OF THESE LISTS
# for i in range(n):
# onestudent = list(map(int, input().split()))
# everything.append(onestudent)
#
#
# country = [0] * 1000 # MAKING EMPTY SPACES TO COUNT OVERLAPPING COUNTRIES
#
# for x in range(2): # CALCULATES FIRST AND SECOND PLACES
# biggest = 0 # BIGGEST SCORE CALCULATING VARIABLE
# whereisfirst = 0 # ROW LOCATION OF FIRST AND SECOND PLACES
# # everything: [0]: country, [1]: number, [2]: score
# for i in range(len(everything)): # BECAUSE THE LENGTH OF EVERYTHING WILL KEEP CHANGING BY I
# if biggest < everything[i][2]: # IF THE VALUE IS BIGGER THAN ORIGINAL BIGGEST
# biggest = everything[i][2] # REPLACE IT (SAVING ON BIGGEST)
# whereisfirst = i # SAVE WHICH ROW HAD WINNERS
#
# print(everything[whereisfirst][0], everything[whereisfirst][1]) # PRINTS THE WINNER'S (COUNTRY, STUDENT NUMBER)
# country[ everything[whereisfirst][0] ] += 1 # IN THE 0000 COUNTRY EMPTY LIST, ADD 1 TO WINNER'S COUNTRY PLACE (ex. country 1 gets saved on the second space (0,1,2,3,~~~))
# everything.pop(whereisfirst) # DELETE THE ROW THAT HAD WINNERS IN EVERYTHING'S LIST
#
# if max(country) == 2: # IF THE MAX 2 OF COUNTRY 0000 LIST IS REACHED
# loc = country.index(max(country)) # LOCATE THE EARLIEST (MAX(COUNTRY)) IN THE LIST / LOCATION IS A VARIABLE (ex. if 0 2 0 0 0 => loc = country 1)
# for i in range(len(everything)): # TEST OUT EVERY LINE OF EVERYTHING
# if everything[i][0] == loc: # IF THE 2+ COUNTRY NUMBER IS ON THE COUNTRY SEAT OF ANY LINE OF EVERYTHING:
# everything[i][2] = 1 # CHANGE THE SCORE TO 1 SO IT WON'T BE ABLE TO COMPETE WITH OTHER SCORES ANYMORE
#
# thirdplacefind = 0
# therowofthird = 0
# for i in range(len(everything)): # CHECK EACH LINE OF EVERYTHING (length because it can change)
# if thirdplacefind < everything[i][2]: # if the pre-existing third place score is smaller than the new score from another line:
# thirdplacefind = everything[i][2] # save the new score over the pre-existing third place score
# therowofthird = i # save the new third place's row
# print(everything[therowofthird][0], everything[therowofthird][1]) # print the country and the student number
#
#
#
#
#
# # Q 4691
# money = 0
# winnermoney = 0
# n = int(input())
# for i in range(n):
# rolled = list(map(int, input().split()))
# rolled.sort()
# if rolled[0] == rolled[1] == rolled[2] == rolled[3]:
# money = 50000 + (rolled[0]*5000)
# if money > winnermoney:
# winnermoney = 0
# winnermoney += money
# if rolled.count(1 or 2 or 3 or 4 or 5 or 6) == 3:
# money = 10000 +
# #
# #
#
# # Q4776 - ?????????????????????????????
# year = int(input())
# number = year % 10
# if year > 2014:
# alphabet = (year - 2014) % 12
# elif year < 2014:
# alphabet = (2014 - year) % 12
# else:
# alphabet = 0
# if alphabet == 1:
# alphabet = 'D'
# elif alphabet == 2:
# alphabet = 'E'
# elif alphabet == 3:
# alphabet = 'F'
# elif alphabet == 4:
# alphabet = 'G'
# elif alphabet == 5:
# alphabet = 'H'
# elif alphabet == 6:
# alphabet = 'I'
# elif alphabet == 7:
# alphabet = 'J'
# elif alphabet == 8:
# alphabet = 'K'
# elif alphabet == 9:
# alphabet = 'L'
# elif alphabet == 10:
# alphabet = 'A'
# elif alphabet == 11:
# alphabet = 'B'
# elif alphabet == 12:
# alphabet = 'C'
# print(alphabet, number, sep='')
Q4751 very hard long question