The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the prefixes can be the full name. Typically there are multiple possible logins for each person.

You are given the first and the last name of a user. Return the alphabetically earliest login they can get (regardless of other potential Polygon users).

As a reminder, a prefix of a string s is its substring which occurs at the beginning of s: "a", "ab", "abc" etc. are prefixes of string "{abcdef}" but "b" and 'bc" are not. A string a is alphabetically earlier than a string b, if a is a prefix of b, or a and b coincide up to some position, and then a has a letter that is alphabetically earlier than the corresponding letter in b: "a" and "ab" are alphabetically earlier than "ac" but "b" and "ba" are alphabetically later than "ac".


-----Input-----

The input consists of a single line containing two space-separated strings: the first and the last names. Each character of each string is a lowercase English letter. The length of each string is between 1 and 10, inclusive. 


-----Output-----

Output a single string — alphabetically earliest possible login formed from these names. The output should be given in lowercase as well.


-----Examples-----
Input
harry potter

Output
hap

Input
tom riddle

Output
tomr

Difficulty: interview

Starter code:

Solutions:
from collections import *
import itertools
import sys

def main():
    a, b = input().split()
    ans = a + b
    n = len(a)
    m = len(b)
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            c = a[:i] + b[:j]
            # print(c)
            ans = min(ans, c)
    print(ans)

main()


import sys
a, b = list(map(str, input().split()))
arr = []
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        arr.append(a[:i] + b[:j])
arr.sort()
print(arr[0])


s = input().split()
d = set()
for i in range(1, len(s[0]) + 1):
	for j in range(1, len(s[1]) + 1):
		d.add(s[0][:i] + s[1][:j])
print(sorted(d)[0])

a, b = input().split()

l = []

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        l.append(a[:i] + b[:j])

l.sort()

print(l[0])


a,b = input().split()
n=len(a)
m=len(b)
names = []
for i in range(n):
    for j in range(m):
        names.append(a[:i+1]+b[:j+1])
print(min(names))


a, b = input().split()

best = None
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        username = a[:i] + b[:j]
        if best is None or username < best:
            best = username

print(best)


a,b=input().split()
ans=[]
for x in range(1,len(a)+1):
    for y in range(1,len(b)+1):
        ans.append(a[:x]+b[:y])
ans=sorted(ans)
print(ans[0])

a,b = input().split()
print(min(a[:i+1]+b[:j+1] for i in range(len(a)) for j in range(len(b))))


a, b = input().split()
ans = a[0]
for i in range(1, len(a)):
    if a[i] < b[0]:
        ans += a[i]
    else:
        break
ans += b[0]
print(ans)

s1, s2 = input().split()
a = []
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        a.append(s1[:i] + s2[:j])
a.sort()
print(a[0])


s, t = input().split()

l = []
for i in range(len(s)):
	for j in range(len(t)):
		l.append(s[:i+1] + t[:j+1])
l.sort()

print(l[0])


q,w=input().split()
s=q[0]
q=q[1:]
while len(q)>0:
    if q[0]<w[0]:
        s+=q[0]
        q=q[1:]
    else:
        q=''
print(s+w[0])


name, fam = input().split()
ans = name[0]
for ch in name[1:]:
    if ch < fam[0]:
        ans += ch
    else:
        break
ans += fam[0]
print(ans)


a, b = input().split()
k = 1
for i in range(1, len(a)):
    if a[i] < b[0]:
        k += 1
    else:
        break
ans = a[:k] + b[0]
print(ans)

a, b = input().split()
ans = "z" * 100
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[:i] + b[:j] < ans:
            ans = a[:i] + b[:j]
print(ans)

s1,s2=input().split()
minn='zzzzzzzzzzzzzzzzz'
for i in range(1,len(s1)+1):
  for j in range(1,len(s2)+1):
    if s1[:i]+s2[:j] <minn:
      minn=s1[:i]+s2[:j]
print(minn)

n, ln = [i for i in input().split(' ')]

ans = n[0]

i = 1

while i < len(n) and n[i] < ln[0]:
    ans += n[i]
    i += 1

ans += ln[0]
print(ans)


a,b = input().split()
ans = a[0]
for i in range(1, len(a)):
	if(a[i] < b[0]):
		ans += a[i]
	else:
		break
ans += b[0]
print(ans)

name, surname = input().split()

ans = name[0] + surname[0]
for i in range(len(name)):
    cur_ans = name[:i + 1]
    for j in range(len(surname)):
        cur_ans += surname[:j + 1]
        ans = min(ans, cur_ans)

print(ans)

name, surname = input().split()
ans = name[0]
for i in name[1:]:
    if i < surname[0]:
        ans += i
    else:
        break
ans += surname[0]
print(ans)

(st1,st2) = (input().split())
d = 0
for i in st1:
	if i<st2[0] or not d:
		d = 1
		print(i, end='')
	else:
		break
print(st2[0])

n, s = input().split()
last = s[0]
ans = n[0]
for x in n[1:]:
    if x<last:
        ans+=x
    else:
        break
print(ans+last)

s1,s2=input().split()
a=[]
for i in range(1,len(s1)+1):
    for j in range(1,len(s2)+1):
        a.append(s1[:i]+s2[:j])
print(min(a))


a, b = list(map(str, input().split()))
an = -1
for i in range(len(a)):
    for j in range(len(b)):
        c = int(i == -1) + int(j == -1)
        if (an == -1 or a[0:i + 1] + b[0: j + 1] < an):
            an = a[0:i + 1] + b[0: j + 1]
print(an)