Which text did it come from?

A generative model can also judge data: the model that gives a word the higher probability is the more likely source. Compare two letter models.

What to build

A program that scores words under two smoothed letter models and says which model each word most likely came from.

Requirements

  • Each model is learned from its text over the alphabet a to z: P(c) = (count of c + 1) / (number of letters + 26), spaces ignored.
  • A word's score is Σ ln P(c) over its letters.
  • Print WORD: A SA, B SB -> M with the scores to 3 decimal places and M the model with the higher score (A on a tie).

Input

Line 1: text A. Line 2: text B. Line 3: q. Then q words.

Output

One line per word.

Constraints

Texts and words use lower-case letters (and spaces in texts); 1 ≤ q ≤ 100.

Example

Input:

aaab
bbbc
2
ab
bc

Output:

ab: A -4.723, B -5.416 -> A
bc: A -6.109, B -4.723 -> B

Why it works

The probability of a word under a model is the product of its letters' probabilities, so adding logs compares the two products without them becoming too small to store; adding 1 to every count keeps unseen letters possible.

Examples

Example 1 · Input
aaab
bbbc
2
ab
bc
Expected output
ab: A -4.723, B -5.416 -> A
bc: A -6.109, B -4.723 -> B
Example 2 · Input
x
y
1
z
Expected output
z: A -3.296, B -3.296 -> A

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each text, count its letters (spaces ignored); a letter's probability is (count + 1) / (letters in the text + 26).

Hint 2

A word's score under a model is the sum of the natural logs of its letters' probabilities.

Hint 3

The higher (less negative) score wins; on a tie, A.

Solution

Show one correct solution (try it yourself first)
import math

texts = [input().replace(" ", ""), input().replace(" ", "")]
q = int(input())


def score(word, text):
    return sum(math.log((text.count(c) + 1) / (len(text) + 26)) for c in word)


for _ in range(q):
    word = input().strip()
    sa, sb = score(word, texts[0]), score(word, texts[1])
    print(f"{word}: A {sa:.3f}, B {sb:.3f} -> {'A' if sa >= sb else 'B'}")

Lesson: What generative AI is →