Aa

Time limit1sMemory limit1024 MB

Summary

Given a list of words, decide whether some choice of aa pairs read as one letter Å (sorted after z) makes the whole list sorted.

Level: Medium6 of 10
Topics: Greedy, String, Implementation
Solved: No attempts yet

Problem

The letter Å is a relatively new invention in the Danish alphabet, introduced only in 1948. Before that, the digraph Aa was used instead. It survives in town names like Aabenraa and Aarhus.

When sorting Danish words, Å is treated as the last letter of the alphabet. Interestingly, this partially extends to the digraph: Aa is sorted like Å, but only when it represents a single sound. Thus, while Aarhus (pronounced "Århus") sorts after Zurich, and afrikaans sorts after afrikan, kontraalt ("kontra-alt") comes before kontrabas.

Given a list of made-up words that could be pronounced in any way, determine whether the list can be sorted.

Input

The first line contains an integer $N$ , the number of words. The next $N$ lines each contain a non-empty string made of characters from a-z, the list of words.

All words are unique.

Output

If it is possible to choose a set of non-overlapping occurrences of aa in the words, to be read as Å, such that the whole list becomes sorted, output yes. Otherwise, output no.

Hint

In the first sample, we compare aarhus and aahus. If the a's in aarhus are pronounced separately, but the a's in aahus make up a single sound, the word list becomes sorted.

In the second sample, no matter how the a's are read, the list is unsorted.

In the third sample, the list is unsorted in every case. If aa is pronounced as two sounds, the first two words are out of order. If it is pronounced as one sound, the last two words are out of order.

In the fourth sample, the list is sorted if it is read as aaaay, aaårecord, aaårghhhh, aåargh, åaahhh, ååbattery, where each å stands for an aa that makes up a single sound.

In the fifth sample, no reading produces a sorted list.

Examples5

Example 1
Input
```
2
aarhus
aahus
```
Expected output
```
yes
```
Example 2
Input
```
2
raaaa
ra
```
Expected output
```
no
```
Example 3
Input
```
3
b
aa
c
```
Expected output
```
no
```

Example 4

Input

6
aaaay
aaaarecord
aaaarghhhh
aaaargh
aaaahhh
aaaabattery

Expected output

yes

Example 5

Input

6
aaaay
aaaarghhhh
aaaargh
aaaarecord
aaaahhh
aaaabattery

Expected output

no