CSES - Aalto Competitive Programming 2024 - wk11 - Wed - Hacking hashes

Time limit: 1.00 s
Memory limit: 512 MB

Maija and Uolevi are participating in an online contest together. One of the tasks requires string matching, which Uolevi has implemented with a rolling hash function. Uolevi's hashing function for string $s$ of length $n$ is:

$F(s) = (\sum_{i=1}^{n}{s_i \times A^{n-i}})\ \mathrm{mod}\ B$

$s_i$ is interpreted as the ASCII code of the character so $a = 97,\ b = 98\ \dots\ z = 122$ .

In C++ this is:

int F(string s) {
    long long h = 0;
    for (chat c : s) h = (h * A + c) % B;
    return h;
}

and in Python:

def F(s):
    h = 0
    for c in s:
        h = (h * A + ord(c)) % B
    return h

Points are awarded to contestants who find failing test cases for other people's solutions so Maija immediately hacks Uolevi's solution by finding two different nonempty strings that have the same hash.

Formally, find two nonempty strings $x$ and $y$ consisting of lowercase Latin letters such that $F(x) = F(y)$ and $x \neq y$ .

Input

A single line contains two integers $A$ and $B$ .

Output

Print $x$ and $y$ in a line separated by a single space.

Constraints

$1 \leq A, B \leq 10^9+7$

Example 1

Input:

1 4

Output:

oheo yzzzeszzyc

Example 2