def longest_common_prefix(strings):
    if not strings:
        return "Invalid input"
    
    # Sort the strings to bring similar prefixes together
    strings.sort()
    
    first = strings[0]
    last = strings[-1]
    i = 0
    
    # Compare characters between the first and last string
    while i < len(first) and i < len(last) and first[i] == last[i]:
        i += 1
    
    prefix = first[:i]
    return prefix if prefix else "Invalid input"

# Main function to handle input and output
def main():
    try:
        N = int(input("Enter number of strings: "))
        if N < 1 or N > 100:
            print("Invalid input")
            return
        
        words = input("Enter the strings separated by space: ").split()
        
        if len(words) != N or any(len(word) > 100 for word in words):
            print("Invalid input")
            return
        
        result = longest_common_prefix(words)
        print(result)
    
    except Exception:
        print("Invalid input")

# Run the program
if __name__ == "__main__":
    main()