A harbor authority arranges n signal buoys in a single line, numbered 0 through n-1 from the shore outward. Buoy i continuously repeats its own blink code -- a short string of lowercase English letters, one letter per blink slot. If you imagine writing buoy i's code across row i of a grid (one letter per column, starting at column 0), the buoys together fill in a grid of letters; a row may be shorter than another, so some grid cells are simply undefined for that row.

The harbourmaster calls the arrangement mirror-true if, for every buoy i and every column j at which row i has a defined letter, two things hold: buoy j must exist (0 <= j < n), and the letter buoy j shows in its own column i must be defined and identical to the letter buoy i shows in column j. Informally, reading down the buoys' codes column-by-column must reproduce the same letters as reading along the buoys' codes row-by-row, wherever a letter is defined on either side.

Given the n blink codes, determine whether the arrangement is mirror-true.

Input format

Line 1: an integer n -- the number of buoys. The next n lines: the blink code of buoy i (0-indexed), a non-empty string of lowercase English letters.

Output format

Print true if the arrangement is mirror-true, or false otherwise.

Constraints

• 1 <= n <= 500
• 1 <= length of each blink code <= 500
• Every blink code consists only of lowercase English letters ('a'-'z').

3
aba
bab
aba

true

2
ab
cd

false