You reached your school! In your math class, you learnt about number base systems. However, you already learnt all of them at the age of six, so you thought, "They are so basic, aren't they?". To not be basic (i.e. acidic), you thought of this problem:

You are given a string $s$ of alphabets and numbers. Each character encode a value:

• The numbers have the same value as their number.
• A $=10$, B $=11$, $\dots$, Z $=35$
• a $=36$, b $=37$, $\dots$, z $=61$

You are also given a target number in decimal, $x$. Your goal is to find a rearrangement of the given string, and a base $b$ ($2 \le b \le 62$), so that the string in base $b$ is equal to the target $x$.

Input

The first line consists of the string $s$ and the target $x$.

Output

If there is an answer, output the rearranged string and then the base $b$ in one line. Otherwise, output Acidic.

Constraints

For all test cases: $1 \le |s| \le 10^6, 1 \le x \le 10^{18}$.
Subtask 1 (25%): $|s| \le 10, b = 10, x \le 10^9$
Subtask 2 (75%): No other constraints