Longest Common Prefix

EasyStringsPrefix5 hidden tests

You are given n lowercase words. Find the longest string that is a prefix of every one of them.

Input format

Line 1: an integer n, the number of words. Line 2: n space-separated lowercase words.

Print the longest common prefix on its own line. If there is no common prefix, print an empty line.

Example 1

Input

3
flower flow flight

Expected

fl

Explanation

All three start with 'fl'; the fourth character differs (o vs i), so the longest common prefix is 'fl'.

Example 2

Input

2
dog cat

Expected

(empty)

Explanation

The two words share no starting character, so the common prefix is empty.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.