Problem F
Hackenbush Simplicity
Languages
en
is
When calculating the values of Hackenbush positions a particular operation comes up quite a lot. It takes two dyadic fractions $x, y$ and produces another dyadic fraction. If there exists an integer $z$ such that $x < z < y$ then the operation returns an integer, the integer $z$ satisfying $x < z < y$ that has the least absolute value. If no such integer exists the operation returns the dyadic fraction $p/2^q$ satisfying $x < p/2^q < y$ having the lowest power $q$ in the denominator. This fraction is uniquely determined.
All fractions in this problem are given in the format x/2q where $x, q$ are integers, additionally $q \geq 0$. If the fraction is an integer /20 is omitted. These fractions are always fully reduced.
Input
The input is two lines, each containing a fraction in the format described above. These fractions are the values $x, y$ which are the inputs of the operation described above. You may assume $x < y$. The exponent in the denominator will be at most $10^9$ and the numerator will have at most $10^4$ digits.
Output
Print the output of applying the operation to $x, y$. Print it in the format described above.
| Sample Input 1 | Sample Output 1 |
|---|---|
3/2^2 7/2^3 |
13/2^4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
-1/2^2 1/2^9 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
9/2^2 19/2^2 |
3 |
| Sample Input 4 | Sample Output 4 |
|---|---|
1 2 |
3/2^1 |
