Problem A
Master Theorem

Many Divide and Conquer (D&C) algorithms have time complexities that can be characterized as the following standard recurrence: $T(n) = a \cdot T(n/b) + c \cdot n^ d \log ^ k n$. Note that $c \cdot n^ d \log ^ k n$ is just the general form of $f(n)$ so that we can capture as many forms of function $f(n)$ as possible. We have just learned about the master theorem. Master theorem has three possible cases:

1. If there exists a constant $\epsilon > 0$ such that $f(n) = O(n^{\log _ b a - \epsilon })$, then $T(n) = \Theta (n^{\log _ b a})$

2. If there exists a constant $k$ such that $f(n) = \Theta (n^{\log _ b a} \log ^ k n)$, then:

   1. If $k \geq 0$, then $T(n) = \Theta (n^{\log _ b a} \log ^{k+1} n)$

   2. If $k = -1$, then $T(n) = \Theta (n^{\log _ b a} \log \log n)$

   3. If $k < -1$, then $T(n) = \Theta (n^{\log _ b a})$

3. If there exists a constant $\epsilon > 0$ such that $f(n) = \Omega (n^{log_ b a + \epsilon })$, and if $f(n)$ additionally satisfies the regularity condition $a \cdot f(n/b) \leq C \cdot f(n)$ for some constant $C < 1$ and all sufficiently large $n$, then $T(n) = \Theta (f(n))$

Now it is time to master the master theorem, by writing a program that can automatically churn out the asymptotic time complexity in the following format: "n^x log^k n" or n^x log log n (without the quotes). Obviously, we want our output format to be as nice as possible for human readers, so here are some additional formatting requirements.

For $x$:

• If $x = 0$, print nothing instead of "n^0".

• If $x = 1$, print "n" instead of "n^1".

• If $x$ is an integer, do not print any trailing decimal points, i.e., print "n^2" instead of "n^2.0".

• Otherwise, round $x$ to the nearest tenth and print that, i.e., print "n^1.5" instead of "n^1.45", print "n^2.8" instead of "n^2.807354", etc.

For $k$:

• If $k = 0$, print nothing instead of "log^0 n".

• If $k = 1$, print "log n" instead of "log^1 n".

Please ensure there are no leading nor trailing space(s) in your output other than a single space between "n^x" and ("log^k n" or "log log n"), if both of them are present.

Input

Each test case contains five numbers: integer $a$, floating-point $b$, floating-point $c$, floating-point $d$, and integer $k$ as denoted in the problem description ($0 < a$, $c \leq 77$; $1 < b \leq 77$; $0 \leq d \leq 77$; $-77 \leq k \leq 77$). Floating-point numbers $b$, $c$, $d$ have at most 7 digits after decimal point.

Output

Print the required answer in one line. However, if master theorem is not actually applicable for the given test case, print "not applicable" (without the quotes) instead.

Subtasks

1. ($19$ Points): All test cases in this subtask fall into case 1 of master theorem, e.g., Sample Input 1.

2. ($22$ Points): All test cases in this subtask fall into case 2 of master theorem and $k \geq 0$, e.g., Sample Input 2.

3. ($21$ Points): All test cases in this subtask fall into case 3 of master theorem, e.g., Sample Input 3.

4. ($15$ Points): All test cases in this subtask has $k < 0$, e.g., Sample Input 4.

5. ($23$ Points): No additional constraints. There are $23$ test cases in this subtask and each correct answer worth 1 point.

4 2.0 2.1 0.0 0

n^2

2 2.0 2.8 1.0 0

n log n

4 2.0 1.3 3.0 0

n^3

2 2.0 2.8 1.0 -1

n log log n