<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

330. Numbers
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Young Andrew is playing yet another numbers game. Initially, he writes down an integer A. Then, he chooses some divisor d1 of A, 1 < d1 < A, erases A and writes A1=A+d1 instead. Then, he chooses some divisor d2 of A1, 1 < d2 < A1, erases A1 and writes A2=A1+d2 instead.

I.e., at any step he chooses some positive integer divisor of the current number, but not 1 and not the whole number, and increases the current number by it.

Is it possible for him to write number B if he started with number A?

Input
The only line of input contains two integers A and B, 2 ≤ A < B ≤ 1012.

Output
If there's no solution, output "Impossible" (without quotes) to the only line of output. If there's one, output the sequence of numbers written starting with A and ending with B, one per line. You're not asked to find the shortest possible sequence, however, you should find a sequence with no more than 500 numbers. It is guaranteed that if there exists some sequence for the given A and B, then there exists a sequence with no more than 500 numbers in it.

Example(s)
sample input
sample output
12 57
12
16
24
27
30
40
50
52
54
57

sample input
sample output
3 6
Impossible

<|response|>
1. Abridged problem statement
-----------------------------

You are given two integers `A` and `B` with `2 ≤ A < B ≤ 10^12`.

You start from the number `A`. In one move, if the current number is `x`, you must:

- choose a divisor `d` of `x` such that `1 < d < x`, and
- replace `x` with `x + d`.

You may repeat this operation any number of times.

Task:

- Output `"Impossible"` if you cannot reach exactly `B` from `A`.
- Otherwise, output **one valid sequence** of numbers starting at `A` and ending at `B` (inclusive), each consecutive pair following the rule above.
- The sequence length must be at most 500 numbers (including `A` and `B`).

You do not need the shortest path; any correct one with ≤ 500 numbers is fine.

---

2. Key observations
-------------------

1. **Prime numbers are dead ends**
   If `x` is prime, its only divisors are `1` and `x` itself, both forbidden.
   So from a prime `x`, **no move is possible**.

2. **Parity behavior (odd/even transitions)**
   - All divisors of an odd number are odd.
     So from an odd `x`, any allowed `d` is odd → `x + d` is even.
   - All divisors of an even number are even (since `2 | x` and any divisor shares this factor).
     So from an even `x`, any allowed `d` is even → `x + d` is even.

   Therefore:
   - After at most one move, you get to an even number.
   - Once you are at an even number, you will stay even forever.

   Consequences:
   - The sequence can be:
     `odd (maybe) → even → even → ... → even`
   - If `B` is odd and is reachable, the **last** move must land on `B` from some even number.

3. **Handling odd endpoints with smallest divisor**
   Define:

   - `min_divisor(x)` = smallest divisor `d` with `1 < d < x`, or `-1` if `x` is prime.

   Then:
   - If `A` is odd and composite (so `min_divisor(A) ≠ -1`), we can first move:
     `A → A + min_divisor(A)` (this is even).
   - If `B` is odd and composite, any valid last move into `B` must be of the form:
     `X → B`, where `X + d = B` and `d` is a proper divisor of `B`.
     One natural choice: use `d = min_divisor(B)`. Then `X = B - d`.

   So we define:
   - `adjusted_A = A` if A is even, else `A + min_divisor(A)` (first move).
   - `adjusted_B = B` if B is even, else `B - min_divisor(B)` (last-but-one).

   Between `adjusted_A` and `adjusted_B` we want an **even → even** sequence.

4. **When is it impossible?**
   - If `A` is odd prime: `min_divisor(A) == -1`. Cannot make the first move.
   - If `B` is odd prime: `min_divisor(B) == -1`. Cannot have a last move to `B`.
   - If after adjusting: `adjusted_A > adjusted_B`, then we can't "walk" upward from `adjusted_A` to `adjusted_B`.

   In any of these situations, the answer is `"Impossible"`.

5. **Core problem: even A to even B**
   Now assume:
   - `adjusted_A` and `adjusted_B` are both even,
   - `adjusted_A ≤ adjusted_B`.

   We must transform one even number into another using steps `+d` where `d` is a proper divisor.

   Strategy: **only use powers of two** as divisors: `d = 2^K`.

   For a move from current `x`:
   - `2^K` must divide `x`, i.e., `x % 2^K == 0`.
   - `2^K` must be proper: `1 < 2^K < x` → `K ≥ 1` and `2^K < x`.
   - `x + 2^K ≤ B` to not overshoot.

   If we can always pick such a power of two, we can progress until we reach `B`.

6. **Why powers of two suffice and keep steps ≤ 500**
   For even `A < B`:

   - There always exists some `K ≥ 1` such that `2^K | A`, `2^K < A`, and `A + 2^K ≤ B` (if not, we'd already be at or beyond B).
   - Among all valid `K`, choose the **largest**. Then perform `A ← A + 2^K`.
   - Two types of steps:
     1. **Divisibility-limited**: we can't increase `K` further because `2^{K+1}` does not divide `A`.
        - After adding `2^K`, the new value becomes divisible by `2^{K+1}`.
        - So next time we may use a strictly larger power of two.
        - This can happen at most `O(log A)` times because `K` strictly increases.
     2. **Distance-limited**: we can't increase `K` because `A + 2^{K+1} > B`.
        - Then the remaining distance `D = B - A` is even.
        - We keep subtracting the largest allowable power-of-two divisors that fit in `D`.
        - This is akin to peeling off bits from the binary representation of `D`, and uses at most `O(log B)` moves.

   Total moves in both phases: `< 2 log₂ B < 500` for `B ≤ 10^12`.

---

3. Full solution approach
-------------------------

1. **Compute smallest non-trivial divisors:**
   - Implement `min_divisor(x)` via trial division up to `sqrt(x)`. Complexity per call is `O(√x)` which is fine for `x ≤ 10^12` (two calls only).

2. **Adjust endpoints for parity:**
   - Read `A`, `B`.
   - Compute `d1 = min_divisor(A)`, `dk = min_divisor(B)`.
   - If `A` is odd:
     - If `d1 == -1` → A is odd prime → `"Impossible"`.
     - Else set `adjusted_A = A + d1`.
   - Otherwise set `adjusted_A = A`.
   - If `B` is odd:
     - If `dk == -1` → B is odd prime → `"Impossible"`.
     - Else set `adjusted_B = B - dk`.
   - Otherwise set `adjusted_B = B`.

3. **Check consistency:**
   - If `adjusted_A > adjusted_B` → output `"Impossible"`.

4. **Solve the even-to-even core:**
   - Now `adjusted_A` and `adjusted_B` are even and `adjusted_A ≤ adjusted_B`.
   - Construct a sequence from `adjusted_A` to `adjusted_B`:

     - Initialize `pw2 = 2`.
     - While `A < B`:
       - While:
         - `A + 2 * pw2 <= B`, and
         - `2 * pw2 < A`, and
         - `A % (2 * pw2) == 0`,
         increase `pw2 *= 2`.
         (This tries to use the largest power of two that both divides `A` and fits under `B`.)
       - While `A + pw2 > B`, shrink `pw2 //= 2` to avoid overshooting.
       - Record current `A` in sequence.
       - Set `A += pw2`.
     - Finally append `B`.

   - This yields an all-even sequence satisfying the step rule.

5. **Rebuild the full path A → B:**
   - Initialize an output list.
   - If `adjusted_A != A` (meaning A was odd and we added one step), then:
     - First output original `A`.
   - Output all numbers from the even sequence (from `adjusted_A` to `adjusted_B`).
   - If `adjusted_B != B` (meaning B was odd and we reserved a last step), then:
     - Output final `B`.

6. **Guarantees:**
   - All consecutive pairs satisfy `next = current + d` where `d` is a valid proper divisor.
   - If a solution exists, this construction finds one with fewer than 500 terms.
   - Otherwise, we correctly print `"Impossible"`.

---

4. C++ implementation
---------------------

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t A, B;

void read() { cin >> A >> B; }

vector<int64_t> solve_even(int64_t A, int64_t B) {
    assert(A % 2 == 0 && B % 2 == 0);

    int64_t pw2 = 2;
    vector<int64_t> steps;
    while(A < B) {
        while(A + 2 * pw2 <= B && 2 * pw2 < A && A % (2 * pw2) == 0) {
            pw2 *= 2;
        }

        while(A + pw2 > B) {
            pw2 /= 2;
        }

        steps.push_back(A);
        A += pw2;
    }

    steps.push_back(B);
    return steps;
}

int64_t min_divisor(int64_t x) {
    for(int64_t d = 2; d * d <= x; d++) {
        if(x % d == 0) {
            return d;
        }
    }

    return -1;
}

void solve() {
    // The first thing we notice is that we don't want the shortest solution,
    // but just any with <= 500 steps. The constraints for A and B are fairly
    // large at 10^12, so it's unlikely that we can get something directly based
    // on the divisors so that it fits within 500 steps. A common idea in
    // constructive problems like this is to explore powers of 2 and then
    // achieve something that is logarithmic. In particular, let's consider the
    // case where both A < B are even. As A and B are both even, there will be
    // some K >= 1, such that A mod 2^K = 0 and A + 2^K <= B (and 2^K < A due to
    // 1 < d < A). Let us choose the largest such K and make the operation A +=
    // 2^K. There are two cases:
    //
    //     1) The constraint was that K was the largest power of 2. If that is
    //        the case, we know that A mod 2^(K+1) = 2^K. Then after the
    //        operation, A mod 2^(K+1) = 0. This means on the next step we would
    //        be able to choose K + 1.
    //
    //     2) The second constraint was bounding or A+2^K <= B. If this is the
    //        case, it's not hard to observe that we will be done in < K steps
    //        using the same procedure. This is because the difference B-K is
    //        even and the operation represents removing the largest bit from
    //        the binary notation. Note that even after adding 2^K, the
    //        divisibility by all K' < K is still kept which allows us to
    //        perform this algorithm if we always choose the largest K.
    //
    // We can have < log(B) times that we hit case 1, followed by again less
    // than log(B) times of case 2. This is logarithmic and within the 500
    // bound. Hence, we now have a solution for the case of both A and B being
    // even.
    //
    // What about the case when A or B is odd? In this case, all divisors of
    // both A and B are odd. We can notice that we can always get from all even
    // numbers to all other even numbers (apart from corner case of A = 2), so
    // it might make sense to make both A and B even. To do this, let's denote
    // by min_divisor(x) the smallest number d such that x mod d = 0 and 1 < d <
    // x. If A is odd, we will have the first operation be A += min_divisor(A).
    // If B is odd, we will have the last operation be A += min_divisor(B).
    // Clearly, it would be impossible if adjusted_A > adjusted_B, where
    // adjusted_A = A + min_divisor(A), and adjusted_B = B - min_divisor(B).
    //
    // Computing min_divisor(x) can be trivially done in O(sqrt(x)), while
    // the rest of the algorithm has O(log(B)) steps, where each step of finding
    // K can be trivially implemented in O(log(B)) too, although if we reuse the
    // last steps value of K as a start and move it as a pointer, the actual
    // amortized complexity will be just O(log(B)). Either way, this is
    // dominated by the min_divisor(x) computation.

    int64_t d1 = min_divisor(A), dk = min_divisor(B);
    int64_t adjusted_A = A, adjusted_B = B;
    if(A % 2 == 1) {
        adjusted_A = A + d1;
    }
    if(B % 2 == 1) {
        adjusted_B = B - dk;
    }
    if(d1 == -1 || dk == -1 || adjusted_A > adjusted_B) {
        cout << "Impossible" << endl;
        return;
    }

    vector<int64_t> ans = solve_even(adjusted_A, adjusted_B);
    if(adjusted_A != A) {
        cout << A << endl;
    }
    for(int64_t x: ans) {
        cout << x << endl;
    }
    if(adjusted_B != B) {
        cout << B << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

5. Python implementation with detailed comments
-----------------------------------------------

```python
import sys
from math import isqrt

def min_divisor(x: int) -> int:
    """
    Return the smallest non-trivial divisor of x (2 <= d < x),
    or -1 if x is prime.
    """
    # Trial division up to sqrt(x)
    limit = isqrt(x)
    for d in range(2, limit + 1):
        if x % d == 0:
            return d
    return -1  # x is prime

def solve_even(A: int, B: int):
    """
    Solve the problem for even A and even B (A <= B).
    We only use moves that add a power-of-two divisor.
    Returns a list of numbers from A to B, inclusive.
    """
    assert A % 2 == 0 and B % 2 == 0
    seq = []
    pw2 = 2  # current power of two we may add

    while A < B:
        # Try to double pw2 while:
        #  1) A + 2*pw2 <= B     (won't overshoot)
        #  2) 2*pw2 < A          (still a proper divisor)
        #  3) A % (2*pw2) == 0   (2*pw2 divides A)
        while A + 2 * pw2 <= B and 2 * pw2 < A and A % (2 * pw2) == 0:
            pw2 *= 2

        # If pw2 is too big to add, shrink it until it fits.
        while A + pw2 > B:
            pw2 //= 2

        # Record current value.
        seq.append(A)
        # Perform the move.
        A += pw2

    # Finally append B.
    seq.append(B)
    return seq

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    A = int(data[0])
    B = int(data[1])

    d1 = min_divisor(A)
    dk = min_divisor(B)

    adjusted_A = A
    adjusted_B = B

    # Handle odd A: first step A -> A + d1
    if A % 2 == 1:
        if d1 == -1:  # A is odd prime
            print("Impossible")
            return
        adjusted_A = A + d1

    # Handle odd B: last step adjusted_B -> adjusted_B + dk = B
    if B % 2 == 1:
        if dk == -1:  # B is odd prime
            print("Impossible")
            return
        adjusted_B = B - dk

    # Interval must be non-empty
    if adjusted_A > adjusted_B:
        print("Impossible")
        return

    # Now both adjusted_A and adjusted_B are even.
    seq_even = solve_even(adjusted_A, adjusted_B)

    out = []

    # If we changed A, print original A first.
    if adjusted_A != A:
        out.append(str(A))

    # Print the even sequence.
    for x in seq_even:
        out.append(str(x))

    # If we changed B, print final B last.
    if adjusted_B != B:
        out.append(str(B))

    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    main()
```

This Python code mirrors the C++ logic, clearly separating:

- parity / primality preprocessing (`min_divisor`, `adjusted_A`, `adjusted_B`),
- the core even-to-even path construction (`solve_even`),
- and final assembly of the sequence.
