Two Languages

AtCoder

IDabc441_b

Time2000ms

Memory256MB

Difficulty—

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. ## Input The input is given from Standard Input in the following format: $N$ $M$ $S$ $T$ $Q$ $w _ 1$ $w _ 2$ $\vdots$ $w _ Q$ [samples]

Samples

Input #1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

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.

Input #2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

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.

Input #3

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

Output #3

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

API Response (JSON)

{
  "problem": {
    "name": "Two Languages",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc441_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The AtCoder country has two official languages: Takahashi-go and Aoki-go.\nBoth Takahashi-go and Aoki-go use some lowercase English letters to write words in those languages. Takahashi-go uses only the...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments