Lyra Belacqua is a very gifted girl. She is one of a very small set of people capable of reading an alethiometer, more commonly known as The Golden Compass. It has one specific use: to tell the truth. The name in fact, is derived from "Aletheia" meaning truth, and "-ometer", meaning "measuring device".

The alethiometer had four needles, out of which the user would direct three of them to lie over symbols on the face of the device to ask a question. The fourth needle then swung into action and pointed to various symbols one after another, thus telling the answer.

For this problem, consider the alethiometer consisting of symbols : digits '0'-'9' and letters 'A'-'Z'. Learned scholars were debating the age of the Universe, and they requested Lyra to find out the age from the alethiometer. Having asked the question, the fourth needle started spouting out symbols, which Lyra quickly recorded. In that long string of characters, she knows that some substring corresponds to the age of the Universe. She also knows that the alethiometer could have wrongly pointed out atmost one digit (0-9) as a letter (A-Z). She then wonders what is the maximum possible age of the Universe.

Given the set of symbols the alethiometer pointed out, help her find the maximum age of the Universe, which could correspond to a substring of the original string with atmost one letter changed.

Note: We consider a substring to be a contiguous part of the string S 

Also, the alethiometer wrongly reports only a letter. All the digits remain as they are.

-----Input-----

Each input consists of a single string S which is what Lyra recorded from the fourth needle's pointing.

-----Output-----

Output one number, the maximum possible answer.

-----Constraints-----
-  1  ≤ |S|  ≤ 1,000
-  S will only contain digits 0-9 and uppercase Latin letters. 

-----Example-----
Input1:
06454

Input2:
C0D3C43F

Output1:
6454

Output2:
3943

-----Explanation-----

In the first example, there is no choice as to what the number can be. It has to be 6,454.

In the second example, there are a total of 41 possible strings (one for the original, and 10 for changing each letter). You can verify that the maximum number as a substring is got by making the string "C0D3943F".

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
str = input()
l = len(str)
p = 1
maxm = 0
for i in range(0, l):
	ans2 = ''
	ans1 = ''
	if ord(str[i]) >= 65 and ord(str[i]) <= 90:
		p = 0
		j = i - 1
		while True:
			if j >= 0:
				if ord(str[j]) >= 65 and ord(str[j]) <= 90:
					break
				else:
					ans1 = ans1 + str[j]
					j = j - 1
			else:
				break
		j = i + 1
		while True:
			if j < l:
				if ord(str[j]) >= 65 and ord(str[j]) <= 90:
					break
				else:
					ans2 = ans2 + str[j]
					j = j + 1
			else:
				break
	ans = ans1[::-1] + '9' + ans2
	ans = int(ans)
	if ans >= maxm:
		maxm = ans
if p == 1:
	print(int(str))
else:
	print(maxm)


def main():
	res = 0
	ind = 0
	curr = []
	letterflag = False
	chars = list(input())
	for c in chars:
		if c.isalpha():
			if letterflag:
				val = int(''.join(curr))
				res = max(res, val)
				curr = curr[ind:]
			else:
				letterflag = True
			curr.append('9')
			ind = len(curr)
		else:
			curr.append(c)
	val = int(''.join(curr))
	res = max(res, val)
	print(res)
main()


string = input()
max_no = 0
for i in range(len(string)):
	var_occur = 0
	check_no = str()
	j = i
	while j < len(string) and var_occur < 2:
		if string[j].isalpha():
			if var_occur == 0:
				check_no += '9'
				var_occur += 1
			else:
				var_occur += 1
		else:
			check_no += string[j]
		j += 1
	max_no = max(max_no, int(check_no))
print(max_no)


import re
s = input()
s2 = re.sub('[a-zA-Z]', '-', s)
parts = s2.split('-')
if len(parts) == 1:
	print(int(parts[0]))
else:
	nums = []
	for i in range(len(parts) - 1):
		nums.append(int(parts[i] + '9' + parts[i + 1]))
	print(max(nums))


s = input()
m = 0
for i in range(len(s)):
	v = 0
	c = str()
	j = i
	while j < len(s) and v < 2:
		if s[j].isalpha():
			if v == 0:
				c += '9'
				v += 1
			else:
				v += 1
		else:
			c += s[j]
		j += 1
	m = max(m, int(c))
print(m)


p = input()
if len(p) >= 1 and len(p) <= 1000:
	i = 0
	k = 0
	x = 0
	m = 0
	while i < len(p):
		if p[i].isdigit():
			j = i
			c = ''
			k = 0
			if i > 0:
				if p[i - 1].isalpha():
					c = c + '9'
					k = 1
					if i > 1 and p[i - 2].isdigit():
						c = p[i - 2] + c
				if p[i - 1].isdigit() and int(p[i - 1] != 0):
					c = c + p[i - 1]
			while i < len(p):
				if p[i].isdigit():
					c = c + p[i]
				if p[i].isalpha():
					if k == 1:
						break
					k = 1
					c = c + '9'
				i = i + 1
			if int(c) > x:
				x = int(c)
			i = j
		else:
			m = m + 1
		i = i + 1
	if x == 0 and m == len(p):
		print(9)
	else:
		print(x)


s = input()
start = -1
end = -1
a = []
l = len(s)
for i in s:
	a.append(i)
chars = 0
nums = 0
for i in a:
	if i >= 'A' and i <= 'Z':
		chars += 1
	else:
		nums += 1
if chars <= 1:
	ans = ''
	for i in a:
		if i >= '0' and i <= '9':
			ans += i
		else:
			ans += '9'
	print(int(ans))
else:
	temp = []
	for i in range(l):
		if a[i] >= 'A' and a[i] <= 'Z':
			a[i] = '9'
			temp.append(i)
	ans = 9
	st = s[:temp[0]] + '9' + s[temp[0] + 1:temp[1]]
	if st != '' and int(st) > ans:
		ans = int(st)
	l2 = len(temp)
	for i in range(1, l2 - 1):
		x = s[temp[i - 1] + 1:temp[i]] + '9' + s[temp[i] + 1:temp[i + 1]]
		if x != '' and int(x) > ans:
			ans = int(x)
	x = s[temp[l2 - 2] + 1:temp[l2 - 1]] + '9' + s[temp[l2 - 1] + 1:]
	if x != '' and int(x) > ans:
		ans = int(x)
	print(ans)


high = 0
s = input()
for i in range(len(s)):
	gg = ''
	l = 0
	if s[i].isdigit() == True:
		gg += s[i]
	else:
		gg += str(9)
		l = 1
	j = i + 1
	while j < len(s) and (l < 1 or s[j].isdigit() == True):
		if s[j].isdigit() == False:
			gg = gg + str(9)
			l += 1
		else:
			gg += s[j]
		j += 1
	if high < int(gg):
		high = int(gg)
print(high)


t = input()
r = r1 = ''
mx = -1
for i in range(len(t)):
	if t[i] >= 'A' and t[i] <= 'Z':
		r = r1 + '9'
		r1 = ''
	else:
		r = r + t[i]
		r1 = r1 + t[i]
	if int(r) > mx:
		mx = int(r)
print(mx)


a = input()
max = 0
for i in range(len(a)):
	brr = ''
	l = 0
	if a[i].isdigit() == True:
		brr += a[i]
	else:
		brr += str(9)
		l = 1
	j = i + 1
	while j < len(a) and (l < 1 or a[j].isdigit() == True):
		if a[j].isdigit() == False:
			brr = brr + str(9)
			l += 1
		else:
			brr += a[j]
		j += 1
	if max < int(brr):
		max = int(brr)
print(max)