The Grand Adventure

/problems/thegrandadventure/file/statement/en/img-0001.png
Our hero, Jim, is about to embark on his grand adventure. On his way, he’ll encounter three different types of objects: money, incense, and gems. When he encounters an object, he will always put it into his backpack. Unfortunately, he’ll also encounter villains along the way. More specifically, the Banker (who will demand money), the Trader (who demand incense), and the Jeweler (who will demand, of course, jewels). Jim must give each villain one of the kind of item they demand as he encounters them, or else he fails and his adventure is over. Unfortunately, Jim’s backpack isn’t very ergonomic and so he can only reach the item he most recently put in it. In other words, the items below are inaccessible until he’s given away the one on top. Jim would also like arrive at his destination with no extra items in his bag. If he does have items at the end, he’ll consider his adventure a failure.

We’d like to know if Jim will be able to complete his adventure before he even starts!

Input

The first line contains a single integer $n$, $1 \le n \le 5$, the number of adventures. Each of the next $n$ lines contains a single string $a$, a sequence of $\{ \$ , *, |, t, j, b, .\} $. An example of this adventure string is:

....$...$...*..*...|...t...j..j...b..b...

where,

  • $ represents Money

  • | represents Incense

  • * represents Gem

  • t represents a Trader

  • j represents a Jeweler

  • b represents a Banker

  • . represents the Ground (nothing)

and $1 \leq |a| \leq 100$ where $|a|$ is the length of string $a$. There is no limit on the number of items Jim may place in his backpack.

Output

Print YES if Jim is able to finish his adventure and print NO if he is unable to.

Sample Input 1 Sample Output 1
5
.$.b.|.t.*.j.................$$$$$bbbbb||....tt.....
.$.b.|.t.*.j..
................................
.......$....$......*....*.....|......t........j...j.....b..b........
...$.$.$..*..*..*...*..|..*..b.....*******...
YES
YES
YES
YES
NO
Sample Input 2 Sample Output 2
4
........$b...$$..t...*..*...j.........j...
.........*****jjjj...............|tj....
.$.|.*.$.|.*.$.|.*.j.t.b.j.t.b.j.t.b.
...$$..$$..$$..|..$$..b......b....t..bbbbbb.....j...
NO
YES
YES
NO