L. Three machines
time limit per test2 seconds
memory limit per test256 megabytes
Three machines read integers from the inserted cards and print new cards with pairs of positive integers. The first machine reads the card (a;b) and outputs a new card (a + 1;b + 1).The second machine reads the card (a;b), and if both numbers are even integers, outputs the card (a / 2;b / 2). When two cards (a;b) and (b;c) are inserted into the third machine, it outputs the card (a;c). All machines return the inserted cards.

There is a single card (a;b). It is necessary to obtain the card (c;d) or find it impossible.

Input
The first line contains integers a and b. The second line contains c and d (1 ≤ a, b, c, d ≤ 2000). The initial and the final cards are different.

Output
If it is not possible to obtain the required card, output 0. Otherwise print k in the first line — number of times the machines have been used. In the following k lines output usage description in the following format: « <number of the machine> <integers on the first card> [<integers on the second card>] ». If the third machine is used, the second integer on the first card must be equal to the first integer on the second card. k must not exceed 15000.

Examples
InputCopy
2 4
1 3
OutputCopy
3
2 2 4
1 1 2
3 1 2 2 3
InputCopy
4 2
1 1
OutputCopy
0
 i have solution for this task in c++:  #include <bits/stdc++.h>
using namespace std;

// Structure to store information about how a state was reached
struct Info {
    int type; // 1 (Machine 1), 2 (Machine 2), 3 (Machine 3)
    pair<int, int> from1; // For Machine 1 and 2: the previous state
    pair<int, int> from2; // For Machine 3: the two states used
};

// Structure to represent an operation for output
struct Operation {
    int type;
    int x;
    int y;
    int w; // Used only for Machine 3
    int z; // Used only for Machine 3
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a, b; // Initial card
    cin >> a >> b;
    int c, d; // Target card
    cin >> c >> d;

    // Check if the relative ordering invariant is violated
    if( (a > b && c <= d) ||
        (a < b && c >= d) ||
        (a == b && (c == d))) {
        cout << "0";
        return 0;
    }

    // Define the maximum value based on problem constraints
    const int MAX_VAL = 2000;

    // Helper to map a pair (x, y) to a unique index
    auto getIndex = [&](int x, int y) -> int {
        return x * (MAX_VAL + 1) + y;
    };

    // Initialize data structures
    vector<Info> info((MAX_VAL +1) * (MAX_VAL +1), Info());
    vector<bool> visited((MAX_VAL +1) * (MAX_VAL +1), false);

    // To efficiently access pairs with a specific first or second element
    vector<vector<int>> forward_(MAX_VAL +1, vector<int>()); // forward_[x] contains y such that (x, y) exists
    vector<vector<int>> reverse_(MAX_VAL +1, vector<int>()); // reverse_[y] contains x such that (x, y) exists

    // Initialize BFS
    queue<pair<int, int>> q;
    q.push({a, b});
    visited[getIndex(a, b)] = true;
    forward_[a].push_back(b);
    reverse_[b].push_back(a);

    // BFS variables
    bool found = false;
    pair<int, int> target;

    while(!q.empty() && !found){
        pair<int, int> current = q.front(); q.pop();
        int x = current.first;
        int y = current.second;

        // **Machine 1:** (x, y) -> (x+1, y+1)
        int nx = x +1;
        int ny = y +1;
        if(nx <= MAX_VAL && ny <= MAX_VAL){
            int idx = getIndex(nx, ny);
            if(!visited[idx]){
                visited[idx] = true;
                info[idx].type = 1;
                info[idx].from1 = {x, y};
                q.push({nx, ny});
                forward_[nx].push_back(ny);
                reverse_[ny].push_back(nx);
                if(nx == c && ny == d){
                    found = true;
                    target = {nx, ny};
                    break;
                }
            }
        }

        // **Machine 2:** If both even, (x, y) -> (x/2, y/2)
        if(x %2 ==0 && y %2 ==0){
            int nx2 = x /2;
            int ny2 = y /2;
            if(nx2 >=1 && ny2 >=1){
                int idx = getIndex(nx2, ny2);
                if(!visited[idx]){
                    visited[idx] = true;
                    info[idx].type = 2;
                    info[idx].from1 = {x, y};
                    q.push({nx2, ny2});
                    forward_[nx2].push_back(ny2);
                    reverse_[ny2].push_back(nx2);
                    if(nx2 == c && ny2 == d){
                        found = true;
                        target = {nx2, ny2};
                        break;
                    }
                }
            }
        }

        // **Machine 3:** Combine (x,y) with (y,z) to get (x,z)
        for(auto &z : forward_[y]){
            int nx3 = x;
            int ny3 = z;
            if(nx3 >=1 && ny3 >=1 && nx3 <= MAX_VAL && ny3 <= MAX_VAL){
                int idx = getIndex(nx3, ny3);
                if(!visited[idx]){
                    visited[idx] = true;
                    info[idx].type = 3;
                    info[idx].from1 = {x, y};
                    info[idx].from2 = {y, z};
                    q.push({nx3, ny3});
                    forward_[nx3].push_back(ny3);
                    reverse_[ny3].push_back(nx3);
                    if(nx3 == c && ny3 == d){
                        found = true;
                        target = {nx3, ny3};
                        break;
                    }
                }
            }
        }
        if(found) break;

        // **Machine 3:** Combine (w,x) with (x,y) to get (w,y)
        for(auto &w : reverse_[x]){
            int nx4 = w;
            int ny4 = y;
            if(nx4 >=1 && ny4 >=1 && nx4 <= MAX_VAL && ny4 <= MAX_VAL){
                int idx = getIndex(nx4, ny4);
                if(!visited[idx]){
                    visited[idx] = true;
                    info[idx].type = 3;
                    info[idx].from1 = {w, x};
                    info[idx].from2 = {x, y};
                    q.push({nx4, ny4});
                    forward_[nx4].push_back(ny4);
                    reverse_[ny4].push_back(nx4);
                    if(nx4 == c && ny4 == d){
                        found = true;
                        target = {nx4, ny4};
                        break;
                    }
                }
            }
        }
    }

    if(!found){
        // If the target card was not reached
        cout << "0";
        return 0;
    }

    // Reconstruct the sequence of operations by backtracking from the target
    vector<Operation> operations;
    // To avoid processing the same state multiple times during reconstruction
    vector<bool> processed((MAX_VAL +1) * (MAX_VAL +1), false);

    // Use DFS to backtrack operations
    // Implemented iteratively to prevent stack overflow
    stack<pair<int, int>> s;
    s.push(target);
    vector<Operation> temp_ops;

    // Colors for DFS: 0 = unvisited, 1 = visiting, 2 = processed
    vector<int> color((MAX_VAL +1) * (MAX_VAL +1), 0);

    // Lambda function for DFS traversal
    function<void(int, int)> dfs = [&](int x, int y) {
        int idx = getIndex(x, y);
        if (color[idx] == 2) return;
        if (color[idx] ==1){
            // No cycles should exist in this transformation graph
            return;
        }
        color[idx] =1;
        Info current_info = info[idx];
        if(current_info.type ==1 || current_info.type ==2){
            int fx = current_info.from1.first;
            int fy = current_info.from1.second;
            dfs(fx, fy);
            Operation op;
            op.type = current_info.type;
            op.x = fx;
            op.y = fy;
            op.w = 0; // Not used
            op.z = 0; // Not used
            temp_ops.push_back(op);
        }
        else if(current_info.type ==3){
            int fx = current_info.from1.first;
            int fy = current_info.from1.second;
            int sx = current_info.from2.first;
            int sy = current_info.from2.second;
            dfs(fx, fy);
            dfs(sx, sy);
            Operation op;
            op.type =3;
            op.x = fx;
            op.y = fy;
            op.w = sx;
            op.z = sy;
            temp_ops.push_back(op);
        }
        color[idx] =2;
    };

    // Start DFS from the target
    dfs(target.first, target.second);

    // Check if the number of operations exceeds the limit
    if(temp_ops.size() > 15000){
        cout << "0";
        return 0;
    }

    // Output the results
    cout << temp_ops.size() << "\n";
    for(auto &op: temp_ops){
        if(op.type ==1){
            cout << "1 " << op.x << " " << op.y << "\n";
        }
        else if(op.type ==2){
            cout << "2 " << op.x << " " << op.y << "\n";
        }
        else if(op.type ==3){
            cout << "3 " << op.x << " " << op.y << " " << op.w << " " << op.z << "\n";
        }
    }
}
 but it gets tl on test where there is no way to get the answer. so add timer and after 1.5 seconds of search print 0