Longest Common Prefix

Find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string ''. Example: ['flower','flow','flight'] → 'fl' Example: ['dog','racecar','car'] → '' (no common prefix)

Input

Line 1: n (number of strings). Line 2: n space-separated strings.

Output

The longest common prefix (empty string if none).

Sample

3
flower flow flight

Expected

fl