C. Integer Overflow
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Victor completed the solution for the problem and, without waiting for feedback from the team, submitted it to the system.

Upon refreshing the submission page, Victor saw the unpleasant verdict Wrong Answer.

It was unpleasant for two reasons:

  • First, it meant an extra $$$20$$$ minutes of penalty time;
  • Second, Victor had no idea what he had done wrong — and that frustrated him the most!

His teammates Aidar and Begimai noticed this.

They observed that Victor's solution used two integer variables $$$A$$$ and $$$B$$$, after which the result of their multiplication $$$C = A \cdot B$$$ was computed.

Moreover, all three variables were declared as $$$32$$$-bit.

Both Aidar and Begimai suspected that the program was experiencing integer overflow — a situation where the value of an integer does not fit into the specified data type.

  • Aidar suggested that perhaps the values of $$$A$$$ and/or $$$B$$$ themselves do not fit into $$$32$$$ bits.
  • Begimai believed that $$$A$$$ and $$$B$$$ were fine, but their product $$$C$$$ did not fit.
  • In response to both suggestions, Victor remarked that he should have written the solution in Python, where integers have unlimited size.

The team could always rewrite it in Python later — right now they wanted to understand what data types should be used for $$$A$$$, $$$B$$$, and $$$C$$$.

Important Information

  • The problem assumes only three integer types:
    • $$$32$$$-bit type: $$$[-2^{31}; 2^{31} - 1] = [-2147483648; 2147483647]$$$;
    • $$$64$$$-bit type: $$$[-2^{63}; 2^{63} - 1] = [-9223372036854775808; 9223372036854775807]$$$;
    • $$$128$$$-bit type: $$$[-2^{127}; 2^{127} - 1]$$$.
  • If an $$$X$$$-bit integer is multiplied by a $$$Y$$$-bit integer, the result of their product will be computed as a $$$Z$$$-bit number, where $$$Z = \max{(X, Y)}$$$.
Input

The first line contains an integer $$$A$$$ $$$(1 \le A \le 10^{18})$$$ — the value of variable $$$A$$$.

The second line contains an integer $$$B$$$ $$$(1 \le B \le 10^{18})$$$ — the value of variable $$$B$$$.

Output

In the first line, output the integer $$$T_A$$$ — the required number of bits for variable $$$A$$$.

In the second line, output the integer $$$T_B$$$ — the required number of bits for variable $$$B$$$.

In the third line, output the integer $$$T_C$$$ — the required number of bits for variable $$$C$$$.

All three numbers $$$T_A, T_B, T_C$$$ can only take values $$$32$$$, $$$64$$$, or $$$128$$$:

  • At least one of the equalities $$$T_C = T_A$$$ or $$$T_C = T_B$$$ must hold.
  • If multiple correct answers are possible, output the answer with the minimum sum $$$T_A + T_B + T_C$$$.
Examples
Input
20000
100000
Output
32
32
32
Input
1000000
300000
Output
64
32
64
Input
3000000
3000000000000
Output
32
64
64
Input
1000000000000000000
1000000000000000000
Output
128
64
128
Note

A Minute of Useful Information

  • The $$$32$$$-bit integer type in C++ and Java is denoted as int.
  • The $$$64$$$-bit integer type in C++ is denoted as long long.
  • The $$$64$$$-bit integer type in Java is denoted as long.
  • $$$128$$$-bit integer types in C++ and Java depend on the compiler, but their use comes with additional difficulties.
  • The int type in Python has an unlimited number of bits.

First test example

  • $$$A = 2 \cdot 10^4$$$;
  • $$$B = 10^5$$$;
  • $$$C = A \cdot B = 2 \cdot 10^9$$$.

All three numbers fit into a $$$32$$$-bit data type.

Second test example

  • $$$A = 10^6$$$;
  • $$$B = 3 \cdot 10^5$$$;
  • $$$C = A \cdot B = 3 \cdot 10^{11}$$$.

$$$A$$$ and $$$B$$$ fit into a $$$32$$$-bit data type, but $$$C$$$ fits only into a $$$64$$$-bit one.

It is necessary to make either variable $$$A$$$ or $$$B$$$ $$$64$$$-bit.

Third test example

  • $$$A = 3 \cdot 10^6$$$;
  • $$$B = 3 \cdot 10^{12}$$$;
  • $$$C = A \cdot B = 9 \cdot 10^{18}$$$.

$$$A$$$ fits into a $$$32$$$-bit data type, but $$$B$$$ and $$$C$$$ fit only into a $$$64$$$-bit one.

Since $$$B$$$ is already $$$64$$$-bit, $$$A$$$ can remain $$$32$$$-bit.

Fourth test example

  • $$$A = 10^{18}$$$;
  • $$$B = 10^{18}$$$;
  • $$$C = A \cdot B = 10^{36}$$$.

$$$A$$$ and $$$B$$$ fit into a $$$64$$$-bit data type, but $$$C$$$ fits only into a $$$128$$$-bit one.

It is necessary to make either variable $$$A$$$ or $$$B$$$ $$$128$$$-bit.