799. Longest Common Prefix

0

Easy

Develop a function that can identify the longest common prefix string among a given array of strings. If there is no common prefix, the function should return an empty string "".

Input Format

The first line of the input should contain a single integer n, representing the number of strings in the array. The next line should contain n space-separated strings.

Output Format

The function should print the longest common prefix string.

Example

Input

3 aad aas aac

Output

aa

Constraints

The length of the strings in the array is less than 10^5.
Loading...

View Submissions

Console