Double Polynomial Hash Collision

You are given two pairs of integers ( (b_1, p_1) ) and ( (b_2, p_2) ). Your task is to construct any two distinct strings ( s ) and ( t ), each consisting solely of lowercase letters (( a ) to ( z )) and having the same length ( n ) (with (1 \le n \le 10^4)), such that when the following polynomial hash function is applied, the results are identical under both pairs of parameters.

The hash function is defined as

[ H(s) = \left(\sum_{i=0}^{n-1} (s[i]-'a'+1)\cdot b^{n-1-i}\right) \mod p, ]

where the parameters ( b ) and ( p ) are given. In other words, you must have

[ H(s, b_1, p_1) = H(t, b_1, p_1) \quad \text{and} \quad H(s, b_2, p_2) = H(t, b_2, p_2). ]

A reference implementation in C++ for computing the hash is provided below:

int strhash(const string &s, int b, int p) {
    int val = 0;
    for (int i = 0; i < s.length(); i++)
        val = (1ll * val * b + s[i] - 'a' + 1) % p;
    return val;
}

Your solution should output any such pair of strings ( s ) and ( t ) (with ( s \neq t )).

Note: It is guaranteed that under the constraints a collision exists. A common approach is to modify a baseline string (for example, a string consisting only of ( a )’s) in a few positions. In our sample solutions we search over a small number of positions (say, using a modification vector of length ( k )) and choose ( k ) as the smallest integer satisfying (26^k > p_1 \times p_2) (with ( k \ge 2 )); then the two distinct modification vectors yielding the same pair of hash values (when multiplied with appropriate powers of ( b_1 ) and ( b_2 )) provide the answer.

inputFormat

The input consists of a single line containing four space‐separated integers: ( b_1), ( p_1), ( b_2), and ( p_2 ).

outputFormat

Output two lines. The first line should contain the string ( s ), and the second line should contain the string ( t ). Both strings must be of equal length (with length between 1 and 10,000) and satisfy the collision requirements under both hash functions.

sample

3 7 5 11

aaa
baa