就不复述思路和一些证明了，下面给了每一步的说明，建议看了y总思路之后再看

C++

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//扩展欧几里得
ll exgcd(ll a, ll b, ll &x, ll &y) // ax+by=gcd(a,b)  //x, y为待求整数,返回值为gcd(a,b)
{
    if(!b)  //当b = 0时，a和b的最大公约数为a.则x = 1
    {
        x =1, y=0;
        return a;
    }
    //当b ≠ 0时，by+(a mod b)x = gcd(a,b)
    ll gcd = exgcd(b, a%b, y, x);
    //上式化为by+(a - a/b * b)x = gcd(a,b)  ->  ax+b(y - a/b * x) = gcd(a,b)
    //由以上变换得：欧几里得定理每递归一次x不用变,y = y-a/b * x
    y = y - a/b *x ; //y在每轮都被更新

    return gcd;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n, d, x, y;
        cin>>n>>d>>x>>y;
        ll a, b;
        //联系扩展欧几里得算法 ax + by = d 
        ll gcd = exgcd(n, d, a, b );

        if((y-x)%gcd!=0)  //d不能整除y - x则无解
        {
            cout<<"Impossible"<<endl;

        }
        else
        {
            //恢复原式子
            b *= (y-x)/gcd; // ax + by = d  ->  (ax + by) *(y-x)/d = d *(y-x)/d ->  (ax + by) *(y-x)/d = y-x

            //定理：若ax0 + by0 = d 
            //则 ：ax' + by' = d ，其中a' = a / d , b' = b / d
            //则任意一组解为：x = x0 + kb'， y = y0 + ka'  y0就是上面求出的b
            //最小的y(代码中的b)即为最小筋斗数目
            n /= gcd; //这里n就是上式中的a'
            //y = y0 + ka'  y0就是上面求出的b
            b = (b%n+n) % n; //这里防止b的值为负数

            cout<<b<<endl;
        }

    }

    return 0;
}