题目描述

小美有 $n$ 个长度为 $m$ 的字符串，这些串是小美早些年收藏的。

小美将这些串从上往下摆好，他现在想问你，从每个串中都取出一个字符，这些字符构成一个新的字符串。

注意，选出的字符必须按照从上往下的顺序构成一个新的字符串。

现在，小美想问你是否可以从这个字符串中找到一个 "tazige" 字符串。

输入描述

第一行，两个整数 $n, m(1 \leq n,m \leq 1000)$ 。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串表示从上往下的第 $i$ 个字符串。

输出描述

输出 "Yes" 表示可以找到，否则输出 "No" 。

样例

输入

6 3
ata
bab
zbc
ijk
efg
cde

输出

Yes

说明

第1行选择 't'
第2行选择 'a'
第3行选择 'z'
第4行选择 'i'
第5行选择 'g'
第6行选择 'e'

思路：遍历

一个指针指向 s = "tazige" 这个字符串的下标 $idx$，初始从 $0$ 开始。

按字符串输入的顺序来枚举每个输入的字符串，这个字符串中存在 $s[idx]$ 这个字符，则 idx++ ，否则继续枚举下一个字符串。

如果 idx==6，即 $s$ 这个串的所有字符都可以在输入的字符串中按输入顺序在每个字符串中找到一个对应字符，那么就说明可以找到这么一个子序列，否则遍历完所有输入的字符串，idx 仍然小于 6 ，说明找不到。

时间复杂度：$O(nm)$