Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

• S is a string of length 16 consisting of 0 and 1.

Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.

Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.

Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

• n is an integer between 1 and 10^9 (inclusive).

Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

The AtCoder country has two official languages: Takahashi-go and Aoki-go.

Both Takahashi-go and Aoki-go use some lowercase English letters to write words in those languages. Takahashi-go uses only the characters contained in a string S of length N, and Aoki-go uses only the characters contained in a string T of length M.

You are given Q words w _ 1,w _ 2,\ldots,w _ Q that are in the official languages of the AtCoder country. For each word, determine which of the following applies based on the characters contained in that word:

• It is confirmed to be a word in Takahashi-go
• It is confirmed to be a word in Aoki-go
• Neither can be determined

Constraints

• 1\le N\le26
• 1\le M\le26
• S is a string of length N consisting of lowercase English letters.
• The characters in S are arranged in alphabetical order.
• All characters in S are distinct.
• T is a string of length M consisting of lowercase English letters.
• The characters in T are arranged in alphabetical order.
• All characters in T are distinct.
• 1\le Q\le100
• w _ i is a string of length at least 1 and at most 100 consisting of lowercase English letters. (1\le i\le Q)
• w _ i is a word in Takahashi-go or Aoki-go. (1\le i\le Q)
• N,M,Q are integers.

Sample Input 1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

Sample Output 1

Takahashi
Aoki
Unknown
Takahashi
Unknown

For example, all of a, s, h, i are used in Takahashi-go, and h is not used in Aoki-go, so it is confirmed that asahi is a word in Takahashi-go. Thus, print Takahashi on the first line.

Both i and t are used in both Takahashi-go and Aoki-go, so it cannot be determined whether it is a word in Takahashi-go or Aoki-go. Thus, print Unknown on the fifth line.

Sample Input 2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

Sample Output 2

Aoki
Aoki
Takahashi
Takahashi
Unknown

o is not used in Takahashi-go, so the first two words are confirmed to be words in Aoki-go. Thus, print Aoki on the first and second lines.

t and n are not used in Aoki-go, so the following two words are confirmed to be words in Takahashi-go. Thus, print Takahashi on the third and fourth lines.

For the first four words, there is a rule that words ending in shi are Takahashi-go, and words ending in ki are Aoki-go. However, all of k, a, s, h, i are used in both Takahashi-go and Aoki-go, so it is impossible to determine which language the word kashi belongs to based on the characters used. Thus, print Unknown on the fifth line.

Sample Input 3

13 11
defghiqsvwxyz
acejmoqrtwx
15
qhsqzhd
jcareec
wwqxqew
wxqxwex
jxxrtwa
trtqjxe
sqyggse
xxqwxew
xewwxxw
wwqxwex
xqqxqwq
qxxexxe
teqeroc
eeeqqee
vxdevyy

Sample Output 3

Takahashi
Aoki
Unknown
Unknown
Aoki
Aoki
Takahashi
Unknown
Unknown
Unknown
Unknown
Unknown
Aoki
Unknown
Takahashi

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

You will perform an operation Q times on the string S. The i-th operation (1\leq i\leq Q) is represented by a pair of characters (c _ i,d _ i), which corresponds to the following operation:

• Replace all occurrences of the character c _ i in S with the character d _ i.

Print the string S after all operations are completed.

Constraints

• 1\leq N\leq2\times10^5
• S is a string of length N consisting of lowercase English letters.
• 1\leq Q\leq2\times10^5
• c _ i and d _ i are lowercase English letters (1\leq i\leq Q).
• N and Q are integers.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

S changes as follows: atcoder → atcodea → aecodea → aecovea → recover. For example, in the fourth operation, all occurrences of a in S={}aecovea (the first and seventh characters) are replaced with r, resulting in S={}recover.

After all operations are completed, S={}recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where c _ i=d _ i or S does not contain c _ i.

Sample Input 3

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial