시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 8 MB142215.385%

문제

Sophie plans to take over control of the world.  Currently a central computer holds it, but its software has critical bugs.  All that Sophie needs to do to overthrow the computer's rule is to set the value of its variable $z$ to any integer divisible by $m$.

At the moment, the variable $z$ is set to an integer $n$, encoded in binary without leading zeros.  In her basement, Sophie has constructed an ion cannon, whose shot can flip a bit of Sophie's choice in the computer's memory.  Naturally, she is going to target the register holding the variable $z$, and in fact can choose to flip any of its bits with an accurate shot.  The cannon can only flip existing bits in the binary representation (which has no leading zeros!), and cannot be used to insert new bits anywhere in the representation, including either of its ends.  However, any leading ones can be flipped to zeros.  Sophie can shoot as many times as she pleases, but each shot increases the chance of her plot being detected.  Thus, she wants to minimize the number of shots.

Help Sophie in seizing power. Write a program that will read the current value $n$ stored in the variable $z$ and a number $m$ from the standard input, determines the minimum number of shots required to overthrow the computer, the number of distinct integers divisible by $m$ that Sophie can transform $n$ into with the minimum number of shots, and the smallest such integer and prints those three numbers.

입력

In the first and only line of input there are two positive integers separated by a single space: $n$ and $m$ ($1 \le n, m \le 10^{15}$). The former is the initial value of the variable $z$, whereas the latter is the one that the final value of $z$ should be a multiple of.

출력

Three numbers should be printed to the standard output, separated by single spaces: the minimum number of shots to overthrow the computer's rule, the number of distinct $n'$ that ensure overthrowing the computer with the minimum number of shots fired, and the minimum one out of those $n'$.

예제 입력 1

30 7

예제 출력 1

1 2 14

예제 입력 2

69 41

예제 출력 2

3 1 0

힌트

In first example, the variable has value $30$, i.e. $11110_{(2)}$ in binary.  To make it a multiple of $7$, it suffices to shoot once. There are two ways to attain that: by transforming to either $\underline{0}1110_{(2)} = 14$ or $111\underline{0}0_{(2)} = 28$. The first value is the minimum.

In second example, the variable has value $69 = 1000101_{(2)}$.  The only way to make it a multiple of $41$ is by transforming it to $0 = \underline{0}000\underline{0}0\underline{0}_{(2)}$, which requires three shots.

제출할 수 있는 언어

C++17, C11, C99, C++98, C++11, C++14, C++20, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang), C++20 (Clang), C90, C2x, C90 (Clang), C2x (Clang)