Common start of words

Problem

Given n words, print the longest string that is a prefix of every word. If there is none, print NONE.

Example 1

Input

3
flower
flow
flight

Output

fl

All three start with fl.

Example 2

Input

2
dog
car

Output

NONE

Try the problem first. Open one hint at a time.

Hint 1

Compare the words letter by letter, column by column.

Hint 2

zip(*words) gives one tuple of letters per column and stops at the shortest word.

Write your Python code, run it on the examples and submit it to hidden tests.