A. Login Verification

Codeforces

IDCF928A

Time1000ms

Memory256MB

Difficulty—

strings

English · Original

Chinese · Translation

Formal · Original

When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc. Login is an arbitrary sequence of lower and uppercase latin letters, digits and underline symbols («___»). However, in order to decrease the number of frauds and user-inattention related issues, it is prohibited to register a login if it is _similar_ with an already existing login. More precisely, two logins _s_ and _t_ are considered similar if we can transform _s_ to _t_ via a sequence of operations of the following types: * transform lowercase letters to uppercase and vice versa; * change letter «_O_» (uppercase latin letter) to digit «_0_» and vice versa; * change digit «_1_» (one) to any letter among «_l_» (lowercase latin «_L_»), «_I_» (uppercase latin «_i_») and vice versa, or change one of these letters to other. For example, logins «_Codeforces_» and «_codef0rces_» as well as «_OO0OOO00O0OOO0O00OOO0OO_lol_» and «_OO0OOO0O00OOO0O00OO0OOO_1oI_» are considered similar whereas «_Codeforces_» and «_Code_forces_» are not. You're given a list of existing logins with no two _similar_ amonst and a newly created user login. Check whether this new login is _similar_ with any of the existing ones. ## Input The first line contains a non-empty string _s_ consisting of lower and uppercase latin letters, digits and underline symbols («___») with length not exceeding 50 — the login itself. The second line contains a single integer _n_ (1 ≤ _n_ ≤ 1 000) — the number of existing logins. The next _n_ lines describe the existing logins, following the same constraints as the user login (refer to the first line of the input). It's guaranteed that no two existing logins are similar. ## Output Print «_Yes_» (without quotes), if user can register via this login, i.e. none of the existing logins is _similar_ with it. Otherwise print «_No_» (without quotes). [samples] ## Note In the second sample case the user wants to create a login consisting of three zeros. It's impossible due to collision with the third among the existing. In the third sample case the new login is similar with the second one.

在注册社交网络时，用户可以创建自己方便的登录名，以便于分享联系人、打印在名片上等。登录名是由小写和大写拉丁字母、数字和下划线符号（«_»）组成的任意序列。然而，为了减少欺诈和用户疏忽相关的问题，如果一个登录名与已存在的登录名 _相似_，则禁止注册。更准确地说，两个登录名 #cf_span[s] 和 #cf_span[t] 被认为是相似的，如果可以通过以下类型的操作序列将 #cf_span[s] 转换为 #cf_span[t]：例如，登录名 «_Codeforces_» 和 «_codef0rces_» 以及 «_OO0OOO00O0OOO0O00OOO0OO_lol_» 和 «_OO0OOO0O00OOO0O00OO0OOO_1oI_» 被认为是相似的，而 «_Codeforces_» 和 «_Code_forces_» 则不是。你被给定一个已存在登录名的列表，其中任意两个均不 _相似_，以及一个新创建的用户登录名。请检查这个新登录名是否与任何一个已存在的登录名 _相似_。第一行包含一个非空字符串 #cf_span[s]，由小写和大写拉丁字母、数字和下划线符号（«_»）组成，长度不超过 #cf_span[50] —— 即登录名本身。第二行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1 000]）—— 已存在登录名的数量。接下来的 #cf_span[n] 行描述已存在的登录名，其约束条件与用户登录名相同（参见输入的第一行）。保证任意两个已存在的登录名均不相似。如果用户可以使用此登录名注册，即没有任何一个已存在的登录名与其 _相似_，则输出 «_Yes_»（不含引号）。否则输出 «_No_»（不含引号）。在第二个样例中，用户想创建一个由三个零组成的登录名。由于与已存在的第三个登录名冲突，因此无法注册。在第三个样例中，新登录名与第二个登录名相似。 ## Input 第一行包含一个非空字符串 #cf_span[s]，由小写和大写拉丁字母、数字和下划线符号（«_»）组成，长度不超过 #cf_span[50] —— 即登录名本身。第二行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1 000]）—— 已存在登录名的数量。接下来的 #cf_span[n] 行描述已存在的登录名，其约束条件与用户登录名相同（参见输入的第一行）。保证任意两个已存在的登录名均不相似。 ## Output 如果用户可以使用此登录名注册，即没有任何一个已存在的登录名与其 _相似_，则输出 «_Yes_»（不含引号）。否则输出 «_No_»（不含引号）。 [samples] ## Note 在第二个样例中，用户想创建一个由三个零组成的登录名。由于与已存在的第三个登录名冲突，因此无法注册。在第三个样例中，新登录名与第二个登录名相似。

**Definitions** Let $ S $ be the user login string. Let $ L = \{l_1, l_2, \dots, l_n\} $ be the set of existing logins, where each $ l_i $ is a string over the alphabet $ \Sigma = \{a,\dots,z, A,\dots,Z, 0,\dots,9, \_\} $. Define an equivalence relation $ \sim $ on $ \Sigma^* $ such that two strings $ x, y \in \Sigma^* $ are similar ($ x \sim y $) if one can be transformed into the other via a sequence of the following operations: - Replace any lowercase letter with its uppercase equivalent (and vice versa). - Replace digit `0` with letter `O` (and vice versa). - Replace digit `1` with letter `l` (and vice versa). **Constraints** 1. $ |S| \leq 50 $ 2. $ 1 \leq n \leq 1000 $ 3. $ \forall i,j \in \{1,\dots,n\}, i \ne j \Rightarrow l_i \not\sim l_j $ **Objective** Determine whether $ S \sim l_i $ for any $ i \in \{1, \dots, n\} $. Output "Yes" if $ \forall i \in \{1,\dots,n\}, S \not\sim l_i $; otherwise output "No".

Samples

Input #1

1_wat
2
2_wat
wat_1

Output #1

Yes

Input #2

000
3
00
ooA
oOo

Output #2

No

Input #3

_i_
3
__i_
_1_
I

Output #3

No

Input #4

La0
3
2a0
La1
1a0

Output #4

No

Input #5

abc
1
aBc

Output #5

No

Input #6

0Lil
2
LIL0
0Ril

Output #6

Yes

API Response (JSON)

{
  "problem": {
    "name": "A. Login Verification",
    "description": {
      "content": "When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc. Login is an arbitrary sequence of lo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF928A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "When registering in a social network, users are allowed to create their own convenient login to make it easier to share contacts, print it on business cards, etc.\n\nLogin is an arbitrary sequence of lo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在注册社交网络时，用户可以创建自己方便的登录名，以便于分享联系人、打印在名片上等。\n\n登录名是由小写和大写拉丁字母、数字和下划线符号（«_»）组成的任意序列。然而，为了减少欺诈和用户疏忽相关的问题，如果一个登录名与已存在的登录名 _相似_，则禁止注册。更准确地说，两个登录名 #cf_span[s] 和 #cf_span[t] 被认为是相似的，如果可以通过以下类型的操作序列将 #cf_span[s]...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be the user login string.  \nLet $ L = \\{l_1, l_2, \\dots, l_n\\} $ be the set of existing logins, where each $ l_i $ is a string over the alphabet $ \\Sigma = \\{a,\\dots,z, A,\\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments