#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        LL n, d, x, y, a, b;
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);

        int gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd) puts("Impossible");
        else
        {
            b *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (b % n + n) % n);
        }
    }

    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;


int exgcd(int a,int b,int &x, int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);

    y-=a/b*x;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);

        exgcd(a,b,x,y);

        printf("%d %d\n",x,y);
    }
    return 0;

}

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1e5+10;

int a[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++)    scanf("%d", &a[i]);
    sort(a,a+n);

    int ans=0;
    for(int i=0;i<n-1;i++)  ans=__gcd(ans,a[i+1]-a[i]);

    if(ans != 0 )
        cout<<(a[n-1]-a[0]) / ans + 1<<endl;
    else
        cout<<n<<endl;

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 3e5+10;

int n;
LL a[N],s[N];
bool st[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        s[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld", &a[i]);
            s[i] = s[i-1]+a[i];
        }

        LL s0=s[0],sn=s[n];
        if(s0 > sn) swap(s0,sn);
        sort(s,s+n+1);

        for(int i=0;i<=n;i++)
            if(s[i]==s0)
            {
                s0=i;
                break;
            }
        for(int i=n;i>=0;i--)
            if(s[i]==sn)
            {
                sn=i;
                break;
            }

        memset(st, 0, sizeof st);
        int l = 0, r = n;
        for (int i = s0; i >= 0; i -= 2)
        {
            a[l ++ ] = s[i];
            st[i] = true;
        }
        for (int i = sn; i <= n; i += 2)
        {
            a[r -- ] = s[i];
            st[i] = true;
        }
        for(int i=0;i<=n;i++)
            if(!st[i])
                a[l++]=s[i];

        LL res=0;
        for(int i=1;i<=n;i++)   res=max(res,abs(a[i]-a[i-1]));

        printf("%lld\n",res);
    }

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, m;
int a[N];

int main()
{
    scanf("%d%d", &n, &m);
    int k = n + m + 1;
    for (int i = 0; i < k; i ++ ) scanf("%d", &a[i]);

    LL res = 0;
    if (!m)
    {
        for (int i = 0; i < k; i ++ ) res += a[i];
    }
    else
    {
        sort(a, a + k);  // 也可以不排序，找出最大值和最小值即可

        res = a[k - 1] - a[0];
        for (int i = 1; i < k - 1; i ++ ) res += abs(a[i]);
    }

    printf("%lld\n", res);

    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10,MOD=1000000009;

int a[N];
int n,k;

int main()
{
    scanf("%d%d", &n,&k);
    for(int i=0;i<n;i++)    scanf("%d", &a[i]);
    sort(a,a+n);

    int res=1,sign=1;
    int l=0,r=n-1;
    if(k%2)
    {
        res=a[r--];
        k--;
        if(res<0)   sign=-1;
    }

    while(k)
    {
        LL x = (LL)a[l]*a[l+1],y=(LL)a[r-1]*a[r];
        if(x * sign > y * sign)
        {
            res=x % MOD * res % MOD;
            l+=2;
        }
        else
        {
            res=y % MOD * res % MOD;
            r-=2;
        }
        k-=2;
    }
    printf("%d\n",res);

    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 5e5+10;

int n;
int a[N];
long double res,s;

int main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);

    sort(a,a+n);

    long double avg=s/n;
    for(int i=0;i<n;i++)
    {
        double cur=s/(n-i);
        if(a[i] < cur)//如果小于平均数就让他取自身
            cur=a[i];
        res+=(cur-avg)*(cur-avg);
        s-=cur;
    }
    res/=n;
    printf("%.4Lf\n",sqrt(res));

    return 0;

}

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 1e3+10;

int n,d;
struct Segment
{
    double l,r;
    bool operator<(Segment&t)   const
    {
        return r<t.r;
    }
}seg[N];

int main()
{
    scanf("%d%d", &n, &d);
    bool failed = false;
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(y>d) failed = true;
        else
        {
            double len = sqrt(d*d-y*y);
            seg[i].l = x-len, seg[i].r=x+len;
        }
    }
    if(failed)
        puts("-1");
    else
    {
        sort(seg,seg+n);

        int cnt=0;
        double last=-1e20;
        for(int i=0;i<n;i++)
        {
            if(last<seg[i].l)
            {
                cnt++;
                last=seg[i].r;
            }
        }
        printf("%d\n",cnt);
    }

    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6+10;

typedef long long LL;

int a[N];
int n;
LL c[N];


int main()
{
    scanf("%d", &n);

    LL sum=0;
    for(int i=1;i<=n;i++)    scanf("%d", &a[i]),sum+=a[i];

    LL avg = sum/n;
    for(int i=n;i>1;i--)
        c[i]=c[i+1]+avg-a[i];
    c[1]=0;

    sort(c+1,c+n+1);

    LL res=0;
    LL mid=c[(n+1)/2];
    for(int i=1;i<=n;i++)   res+=abs(c[i]-mid);

    printf("%lld\n",res);

    return 0;

}

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int a[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);

    LL ans;
    int c=a[n/2];

    for(int i=0;i<n;i++)    ans+=abs(a[i]-c);

    printf("%lld\n",ans);

    return 0;

}