stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<math.h>

#include<complex>

#include<queue>

#include<deque>

#include<map>

#include<set>

#include<bitset>

using namespace std;

#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; i++ )

#define rep(i,n) REP(i,0,n)

typedef long long ll;

typedef pair<int,int> pint;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;



int n,m,used[101010],cmp[101010];

vector<int> v[101010],rv[101010],vs;



void dfs(int x){

   used[x]=true;

   for(auto to:v[x])if(!used[to])dfs(to);

   vs.push_back(x);

}



void rdfs(int x,int k){

   used[x]=true;

   cmp[x]=k;

   for(auto to:rv[x])if(!used[to])rdfs(to,k);

}



int scc(){

   rep(i,n)if(!used[i])dfs(i);

   rep(i,n)used[i]=0;

   reverse(vs.begin(),vs.end());

   int k=0;

   for(auto x:vs)if(!used[x])rdfs(x,k++);

   return k;

}

int main(){

    cin>>n>>m;

    rep(i,m){

        int s,t;

        cin>>s>>t;

        v[s].push_back(t);

        rv[t].push_back(s);

    }

    scc();

    int q;

    cin>>q;

    rep(i,q){

        int s,t;

        cin>>s>>t;

        cout<<(cmp[s]==cmp[t])<<endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.330003640425155x):
#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

#include<iomanip>

#include<math.h>

#include<complex>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

#include<bitset>

using namespace std;

#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )

#define rep(i,n) REP(i,0,n)

typedef long long ll;

typedef pair<int,int> pint;

typedef pair<ll,int> pli;

const int inf=1e9+7;

const ll longinf=1LL<<60 ;

const ll mod=1e9+7 ;

struct StronglyConnectedComponents{

    vector<int> used,cmp,vs;

    vector<vector<int>> v,rv,g;

    StronglyConnectedComponents(int n):used(n),cmp(n,-1),v(n),rv(n){}



    void add_edge(int x,int y){

        v[x].push_back(y);

        rv[y].push_back(x);

    }

    void dfs(int x){

        used[x]=true;

        for(auto to:v[x])if(!used[to])dfs(to);

        vs.push_back(x);

    }



    void rdfs(int x,int k){

        cmp[x]=k;

        for(auto to:rv[x])if(cmp[to]==-1)rdfs(to,k);

    }



    int scc(){

        rep(i,used.size())if(!used[i])dfs(i);

        reverse(vs.begin(),vs.end());

        int k=0;

        for(auto x:vs)if(cmp[x]==-1)rdfs(x,k++);

        return k;

    }

    void build(){

        int k=scc();

        g.resize(k);

        rep(i,v.size()){

            for(auto& to:v[i]){

                int x=cmp[i],y=cmp[to];

                if(x!=y)g[x].push_back(y);

            }

        }

    }

};

int main(){

    int n,m;

    cin>>n>>m;

    StronglyConnectedComponents scc(n);

    rep(i,m){

        int x,y;

        cin>>x>>y;

        scc.add_edge(x, y);

    }

    scc.scc();

    int q;cin>>q;

    rep(i,q){

        int x,y;

        cin>>x>>y;

        cout<<(scc.cmp[x]==scc.cmp[y])<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<cstring>



using namespace std;



const int MAX_N = 10000;

const int V = 10000;



vector<int> G[MAX_N];

vector<int> rG[MAX_N];

vector<int> vs; //??°?????????????????????

bool used[MAX_N]; //?????§????????????????????????

int cmp[MAX_N];	//?±????????????£????????????????????????????????????



void add_edge(int from,int to)

{

	G[from].push_back(to);

	rG[to].push_back(from);

}



void dfs(int v)

{

	used[v] = true;

	for(int i=0;i<G[v].size();i++){

		if(!used[G[v][i]]){

			dfs(G[v][i]);

		}

	}

	vs.push_back(v);

}



void rdfs(int v,int k)

{

	used[v] = true;

	cmp[v] = k;

	for(int i=0;i<rG[v].size();i++){

		if(!used[rG[v][i]]){

			rdfs(rG[v][i],k);

		}

	}

}



int scc()	//?????£??????????????°?????????

{

	memset(used,0,sizeof(used));

	vs.clear();

	for(int v=0;v<V;v++){

		if(!used[v]){

			dfs(v);

		}

	}

	memset(used,0,sizeof(used));

	int k=0;

	for(int i=vs.size()-1;i>=0;i--){

		if(!used[vs[i]]){

			rdfs(vs[i],k++);

		}

	}

	return k;

}



int main()

{

	int n,m,from,to,k,l,u,v;

	cin >> n >> m;

	for(int i=0;i<m;i++){

		cin >> from >> to;

		add_edge(from,to);

	}

	k = scc();	

	cin >> l;

	for(int i=0;i<l;i++){

		cin >> u >> v;

		printf("%d\n",(cmp[u] == cmp[v]));

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.1536600614933261x):
#include<iostream>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<cstring>



using namespace std;



const int MAX_N = 10000;

const int V = 10000;



vector<int> G[MAX_N];

vector<int> rG[MAX_N];

vector<int> vs; //??°?????????????????????

bool used[MAX_N]; //?????§????????????????????????

int cmp[MAX_N];	//?±????????????£????????????????????????????????????



void add_edge(int from,int to)

{

	G[from].push_back(to);

	rG[to].push_back(from);

}



void dfs(int v)

{

	used[v] = true;

	for(int i=0;i<G[v].size();i++){

		if(!used[G[v][i]]){

			dfs(G[v][i]);

		}

	}

	vs.push_back(v);

}



void rdfs(int v,int k)

{

	used[v] = true;

	cmp[v] = k;

	for(int i=0;i<rG[v].size();i++){

		if(!used[rG[v][i]]){

			rdfs(rG[v][i],k);

		}

	}

}



int scc(int n)	//?????£??????????????°?????????

{

	memset(used,0,sizeof(used));

	vs.clear();

	for(int v=0;v<n;v++){

		if(!used[v]){

			dfs(v);

		}

	}

	memset(used,0,sizeof(used));

	int k=0;

	for(int i=vs.size()-1;i>=0;i--){

		if(!used[vs[i]]){

			rdfs(vs[i],k++);

		}

	}

	return k;

}



int main()

{

	int n,m,from,to,k,l,u,v;

	cin >> n >> m;

	for(int i=0;i<m;i++){

		cin >> from >> to;

		add_edge(from,to);

	}

	k = scc(n);	

	cin >> l;

	for(int i=0;i<l;i++){

		cin >> u >> v;

		printf("%d\n",(cmp[u] == cmp[v]));

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define   ll     long long int



void sortt(ll &a, ll &b, ll &c)

{

    if (a < b) swap(a, b);

    if (b < c) swap(c, b);

    if (a < b) swap(a, b);

}



ll func(ll h, ll w)

{

    ll i, j, k, s = 1e15;

    ll first, second, third;

    ll w_second = w / 2;

    ll w_third = w - w_second;



    for (i = 1; i < h; i++) {

        first = i * w;

        j = h - i;

        second = j * w_second;

        third = j * w_third;

        sortt(first, second, third);

        s = min(s, first - third);



        first = i * w;

        ll h_second = j / 2;

        ll h_third = j - h_second;

        second = h_second * w;

        third = h_third * w;

        sortt(first, second, third);

        s = min(s, first - third);

        //cout << i << ' ' << first << ' ' << second << ' ' << third << '\n';

    }

    return s;

}



int main( )

{

    ll h, w;

    cin >> h >> w;

    if (h % 3 == 0 || w % 3 == 0) {

        cout << "0\n";

        return 0;

    }

    cout << min(func(h, w), func(w, h)) << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.311236337370686x):
/*

    把h*w矩形分为三部分,求最大面积与最小面积之差最小值

    首先,n或m为三的倍数,面积差最小值为0

    其次,暴力枚举所有情况

    先将矩形,分为两部分,横切或者竖切,剩下的那块对半分

    最大h*w会爆int

*/

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll inf = 9e18;

ll Max(ll a,ll b,ll c){

    return max(a, max(b, c));

}

ll Min(ll a,ll b,ll c){

    return min(a, min(b, c));

}

int main(){

    ll h, w, ans;

    scanf("%lld%lld", &h, &w);

    if(!(h%3)||!(w%3)){

        puts("0");

        return 0;

    }

    ans = inf;

    for (ll i = 1; i < h;i++){

        ll tmp = h - i;//剩下部分

        ll h1 = (tmp + 1) / 2;  //向上取整

        ll h2 = tmp / 2;//向下取整

        //为1时不能再横切

        if(tmp!=1){

            ans=min(ans,Max(i*w,h1*w,h2*w)-Min(i*w,h1*w,h2*w));

        }

        ll w1 = (w + 1) / 2;

        ll w2 = w / 2;

        //竖切,w初始为2

        ans=min(ans,Max(i*w,tmp*w1,tmp*w2)-Min(i*w,tmp*w1,tmp*w2));

    }

    for (ll i = 1; i < w;i++){

        ll tmp = w - i;//

        ll w1 = (tmp + 1) / 2;  //向上取整

        ll w2 = tmp / 2;//向下取整

        if(tmp!=1){

            ans=min(ans,Max(i*h,w1*h,w2*h)-Min(i*h,w1*h,w2*h));

        }

        ll h1 = (h + 1) / 2;

        ll h2 = h / 2;

        ans=min(ans,Max(i*h,tmp*h1,tmp*h2)-Min(i*h,tmp*h1,tmp*h2));

    }

    printf("%lld", ans);

    return 0;

}
// Slower C++ solution:
#include<iostream> 

#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)



int main() {

	int n, k, x,y=0;

	cin >> n >> k;

	rep(i, n) {

		cin >> x;

		if (x > k) {

			y += (x - k) * 2;

		}

		else if (k - x < x) {

			y += (k - x) * 2;

		}

		else {

			y += x * 2;

		}

	}

	cout << y << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2497003238962305x):
#include<cstdio>

#include<algorithm>

using namespace std;

const int MAX_N = 100;

int N, K;

int X[MAX_N];

int main(){

scanf("%d", &N);

scanf("%d", &K);

for(int i = 0; i < N; ++i){

scanf("%d", X + i);

}

int ans = 0;

for(int i = 0; i < N; ++i){

int tmp = min(X[i], K - X[i]);

ans += tmp;

}

printf("%d\n", ans * 2);

return 0;

}
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define MAXN 1000010

int  arr[1000];

int brr[101][101]={0};

int main()

{

	int n ;

	cin >>n;

	int sum=0;int pp = 0;

	if(n%2){

        pp = n-1;

	}

	else pp = n;



    for(int i=1;i<=n;i++){

        for(int j =1;j<=n;j++){

                if(j!=pp&&(brr[i][j]==0&&brr[j][i]==0)&&i!=j)

                    brr[i][j]=1,sum++;

        }

        pp--;

    }

    cout<<sum<<endl;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            if(brr[i][j])

                cout<<i<<" "<<j<<endl;

        }

    }

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.242542987214274x):
#include<cstdio>

int n,ans;long long t,f[233];char a[1200][2];

int main(){

	scanf("%d",&n);

	if(n&1){

			for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n) ans++;printf("%d\n",ans);

	for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n) 

	printf("%d %d\n",i,j); 

	}

	else {

		for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n+1) ans++;printf("%d\n",ans);

	for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n+1) printf("%d %d\n",i,j); 

	}



}
// Slower C++ solution:
#include<cstdio>

#include<vector>

using namespace std;

int n;

int main()

{

	scanf("%d", &n);

	int x = (n & 1) ? n : (n + 1);

	vector<pair<int, int>> edges;

	for (int i = 1; i <= n; i++)

	{

		for (int j = i + 1; j <= n; j++)

		{

			if (i + j != x)

			{

				edges.push_back(make_pair(i, j));

			}

		}

	}

	printf("%d\n", edges.size());

	for (auto& p : edges) printf("%d %d\n", p.first, p.second);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.8538093130511974x):
#include<cstdio>

int n,ans;long long t,f[233];char a[1200][2];

int main(){

	scanf("%d",&n);

	if(n&1){

			for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n) ans++;printf("%d\n",ans);

	for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n) 

	printf("%d %d\n",i,j); 

	}

	else {

		for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n+1) ans++;printf("%d\n",ans);

	for(int i=1;i<=n;i++)

	for(int j=i+1;j<=n;j++)

	if(i+j!=n+1) printf("%d %d\n",i,j); 

	}



}
// Slower C++ solution:
#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define MAXN 1000010

int  arr[1000];

int brr[101][101]={0};

int main()

{

	int n ;

	cin >>n;

	int sum=0;int pp = 0;

	if(n%2){

        pp = n-1;

	}

	else pp = n;



    for(int i=1;i<=n;i++){

        for(int j =1;j<=n;j++){

                if(j!=pp&&(brr[i][j]==0&&brr[j][i]==0)&&i!=j)

                    brr[i][j]=1,sum++;

        }

        pp--;

    }

    cout<<sum<<endl;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            if(brr[i][j])

                cout<<i<<" "<<j<<endl;

        }

    }

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.252577282790176x):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

using namespace std;

int n;

int main()

{

	scanf("%d", &n);

	int x = (n & 1) ? n : (n + 1);

	vector<pair<int, int>> edges;

	for (int i = 1; i <= n; i++)

	{

		for (int j = i + 1; j <= n; j++)

		{

			if (i + j != x)

			{

				edges.push_back(make_pair(i, j));

			}

		}

	}

	printf("%d\n", edges.size());

	for (auto& p : edges) printf("%d %d\n", p.first, p.second);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.863099567310438x):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int main() {

    int n;

    cin >> n;





    if (n%2) {

        cout << (n*(n-1))/2 - n/2 << "\n";

        for (int i = 1; i <= n; i++) {

            for (int j = i+1; j <= n; j++) {

                if (i+j==n) continue;

                cout << i << " " << j << "\n";

            }

        }



    } else {

        cout << n*(n-2)/2 << "\n";

        for (int i = 1; i <= n; i++) {

            for (int j = i+1; j <= n; j++) {

                if (i+j==n+1) continue;

                cout << i << " " << j << "\n";

            }

        }

    }





    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.2554888249858065x):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define Maxn 10007

int m,a[Maxn],b[Maxn],c[Maxn];

int n;

int main()

{

    scanf("%d",&n);

    if (n%2==0)

    {

        for (int i=1;i<=n/2;i++)

            c[i]=i,c[n+1-i]=i;

    } else

    {

        for (int i=1;i<=n/2;i++)

            c[i]=i,c[n-i]=i;

        c[n]=n;

    }

    for (int i=1;i<=n;i++)

        for (int j=i+1;j<=n;j++)

            if (c[i]!=c[j])

            {

                ++m;

                a[m]=i;

                b[m]=j;

            }

    printf("%d\n",m);

    for (int i=1;i<=m;i++)

        printf("%d %d\n",a[i],b[i]);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.192177112133113x):
#include <cstdio>

#include <algorithm>

int doing(int n) {

	

}

int main() {

	int n;

	scanf("%d",&n);

	int cnt=0;

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				++cnt;

			}

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=n;++i) {

		for(int j=i+1;j<=n;++j) {

			if(j!=n-i+(n+1)%2) {

				printf("%d %d\n",i,j);

			}

		}

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define pii pair <int, int>

#define fi first

#define sc second

#define ALL(x) x.begin(), x.end()

#define RALL(X) x.begin(), x.end()

#define FOR(i, n, k) for(i=0; i<n; i+=k)

#define FO(i, n, k) for(i=1; i<=n; i+=k)

#define CLEAR(a, b) memset(a, b, sizeof(a))

#define N 100005

#define mid ((l+r)/2)

#define dbg(x) (cerr << #x << " : " << x << endl)

#define endl "\n"

#define MOD 100000009



using namespace std;



typedef long long int lli;



const int NMAX = 1e2 + 5;



vector <pii> res;



int main(){

	ios_base::sync_with_stdio(false);

	int n;

	cin >> n;



	if(n%2 == 0){

		for(int i=1; i<=n; i++){

			for(int j=i+1; j<=n; j++){

				if(j != n-i+1){

					res.pb(mp(i, j));

				}

			}

		}

	}else{

		n--;

		for(int i=1; i<=n; i++){

			for(int j=i+1; j<=n; j++){

				if(j != n-i+1){

					res.pb(mp(i, j));

				}

			}

		}

		n++;

		for(int i=1; i<n; i++)

			res.pb(mp(i, n));

	}



	cout << res.size() << endl;

	for(pii r: res) {

		cout << r.fi << " " << r.sc << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.023912310907334x):
#include <cstdio>

#include <cstring>

bool matrix[105][105];

int arr[105];

int brr[105];

int N;

int main() {

    scanf("%d",&N);

    memset(matrix, true, sizeof(matrix));

    int sum = (N*(N+1)) / 2;

    int base, e;

    printf("%d\n",N*(N-1)/2 - N/2);

    if (N % 2) {

        base = N;

        e = N - 1;

    } else {

        base = N + 1;

        e = N;

    }



    for (int i = 1; i <= e; i++) {

        matrix[i][base - i] = matrix[base - i][i] = false;

    }

     for (int i = 1; i <= N; i++) {

        for (int j = 1; j <= N; j++) {

            if (i == j || !matrix[i][j])

                continue;

            printf("%d %d\n",i, j);

            matrix[i][j] = matrix[j][i] = false;

        }

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct edge{int to;ll cost;};

vector<edge> G[60000];

ll dp[60000];

priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> qu;//dp[],2*(n-1)*c+v



int a,b,c;

int nextv(int v){ return (a*v+b)%c;}



int main(void){

	int n,m,v0;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m); 

	rep(i,m){

		cin>>x[i]>>y[i]>>t[i];

		--x[i];

		--y[i];

	}

	cin>>v0>>a>>b>>c;

	rep(i,m)rep(v,c){

		G[x[i]*c+v].push_back({y[i]*c+nextv(v),t[i]*v});

		G[y[i]*c+v].push_back({x[i]*c+nextv(v),t[i]*v});	

		G[((n-1)*2-x[i])*c+v].push_back({((n-1)*2-y[i])*c+nextv(v),t[i]*v});

		G[((n-1)*2-y[i])*c+v].push_back({((n-1)*2-x[i])*c+nextv(v),t[i]*v});

	}

	rep(i,60000)dp[i]=LLONG_MAX;

	dp[v0]=0;

	qu.push({0,v0});

	while(qu.size()){

		pair<ll,int> u = qu.top();

		qu.pop();

		if(u.second/c==2*(n-1)){

			cout<<dp[u.second]<<endl;

			return 0;			

		}

		if(dp[u.second] < u.first)continue;

		for(auto e:G[u.second]){

			if(dp[e.to] > dp[u.second] + e.cost){

				dp[e.to] = dp[u.second] + e.cost;

				qu.push({dp[e.to],e.to});

			}

		}



	}

	

	// ll res = LLONG_MAX;

	// rep(i,c){

	// 	res = min(res,dp[2*(n-1)*c+i]);

	// }

	// cout<<res<<endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.9481035256410633x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct Trio{

	int to,v;

	ll cost;

	bool operator<(const Trio& right)const{

		return (cost > right.cost);

	}

};

priority_queue<Trio,vector<Trio>> qu;



int a,b,c;

int nextv(int v){ return (a*v+b)%c;}



int main(void){

	int n,m,v0;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m);

	rep(i,m) cin>>x[i]>>y[i]>>t[i];

	cin>>v0>>a>>b>>c;

	vector<Trio> G[(n+1)*2][c];

	ll dp[(n+1)*2][c];

	rep(i,m)rep(v,c){

		G[x[i]][v].push_back({y[i],nextv(v),t[i]*v});

		G[y[i]][v].push_back({x[i],nextv(v),t[i]*v});

		G[n+x[i]][v].push_back({n+y[i],nextv(v),t[i]*v});

		G[n+y[i]][v].push_back({n+x[i],nextv(v),t[i]*v});

	}

	rep(v,c) G[n][v].push_back({n*2,v,0});



	rep(i,(n+1)*2)rep(v,c) dp[i][v]=LLONG_MAX;

	dp[1][v0]=0;

	qu.push({1,v0,0});

	while(qu.size()){

		Trio u=qu.top(); qu.pop();

		if(u.to==n+1){

			cout<<dp[u.to][u.v]<<endl;

			return 0;

		}

		if(dp[u.to][u.v] < u.cost)continue;

		for(auto e:G[u.to][u.v]){

			if(dp[e.to][e.v] > dp[u.to][u.v] + e.cost){

				dp[e.to][e.v] = dp[u.to][u.v] + e.cost;

				qu.push({e.to,e.v,dp[e.to][e.v]});

			}

		}

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct edge{int to;ll cost;};

vector<edge> G[60000];

ll dp[60000];

priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> qu;//dp[],2*(n-1)*c+v



int a,b,c;

int nextv(int v){ return (a*v+b)%c;}



int main(void){

	int n,m,v0;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m); 

	rep(i,m){

		cin>>x[i]>>y[i]>>t[i];

		--x[i];

		--y[i];

	}

	cin>>v0>>a>>b>>c;

	rep(i,m)rep(v,c){

		G[x[i]*c+v].push_back({y[i]*c+nextv(v),t[i]*v});

		G[y[i]*c+v].push_back({x[i]*c+nextv(v),t[i]*v});	

		G[((n-1)*2-x[i])*c+v].push_back({((n-1)*2-y[i])*c+nextv(v),t[i]*v});

		G[((n-1)*2-y[i])*c+v].push_back({((n-1)*2-x[i])*c+nextv(v),t[i]*v});

	}

	rep(i,60000)dp[i]=LLONG_MAX;

	dp[v0]=0;

	qu.push({0,v0});

	while(qu.size()){

		pair<ll,int> u = qu.top();

		qu.pop();

		if(u.second/c==2*(n-1)){

			cout<<dp[u.second]<<endl;

			return 0;			

		}

		if(dp[u.second] < u.first)continue;

		for(auto e:G[u.second]){

			if(dp[e.to] > dp[u.second] + e.cost){

				dp[e.to] = dp[u.second] + e.cost;

				qu.push({dp[e.to],e.to});

			}

		}



	}

	

	// ll res = LLONG_MAX;

	// rep(i,c){

	// 	res = min(res,dp[2*(n-1)*c+i]);

	// }

	// cout<<res<<endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.949334064769461x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)

typedef long long ll;

struct Trio{

	int to,v;

	ll cost;

	bool operator<(const Trio& right)const{

		return (cost > right.cost);

	}

};



int main(void){

	int n,m,v0,a,b,c;

	cin>>n>>m;

	vector<int> x(m),y(m);

	vector<ll> t(m);

	rep(i,m) cin>>x[i]>>y[i]>>t[i];

	cin>>v0>>a>>b>>c;

	vector<Trio> G[(n+1)*2][c];

	ll dp[(n+1)*2][c];

	rep(i,m)rep(v,c){

		int nextv=(a*v+b)%c;

		ll cost=t[i]*v;

		G[x[i]][v].push_back({y[i],nextv,cost});

		G[y[i]][v].push_back({x[i],nextv,cost});

		G[n+x[i]][v].push_back({n+y[i],nextv,cost});

		G[n+y[i]][v].push_back({n+x[i],nextv,cost});

	}

	rep(v,c) G[n][v].push_back({n*2,v,0});



	rep(i,(n+1)*2)rep(v,c) dp[i][v]=LLONG_MAX;

	dp[1][v0]=0;

	priority_queue<Trio,vector<Trio>> qu;

	qu.push({1,v0,0});

	while(qu.size()){

		Trio u=qu.top(); qu.pop();

		if(u.to==n+1){

			cout<<dp[u.to][u.v]<<endl;

			return 0;

		}

		if(dp[u.to][u.v] < u.cost)continue;

		for(auto e:G[u.to][u.v]){

			if(dp[e.to][e.v] > dp[u.to][u.v] + e.cost){

				dp[e.to][e.v] = dp[u.to][u.v] + e.cost;

				qu.push({e.to,e.v,dp[e.to][e.v]});

			}

		}

	}

}
// Slower C++ solution:
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <bits/stdc++.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  ans+=(n-1)*n*(a/m)/2+n*(b/m);

  a%=m;

  b%=m;



  ll y_max=(a*n+b)/m, x_max=(y_max*m-b);

  if(y_max==0) return ans;

  ans+=(n-(x_max+a-1)/a)*y_max;

  ans+=floor_sum(y_max,a,m,(a-x_max%a)%a);

  return ans;

}



int main(){

  int t;

  cin>>t;

  

  rep(i,t){

    int n,m,a,b;

    cin>>n>>m>>a>>b;  

    cout<<floor_sum(n,m,a,b)<<endl;

  }

  

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.151562488598908x):
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#define ALL(v) v.begin(), v.end()

typedef long long ll;



#include <stdio.h>

using namespace std;



ll floor_sum(ll n,ll m,ll a,ll b){

  ll ans=0;

  if(a>=m){

    ans+=(n-1)*n*(a/m)/2;

    a%=m;

  }

  if(b>=m){

    ans+=n*(b/m);

    b%=m;

  }



  ll y_max=(a*n+b)/m;

  if(y_max==0) return ans;

  ans+=floor_sum(y_max,a,m,a*n-y_max*m+b);

  return ans;

}



int main(){

  int t;

  scanf("%d",&t);

  

  while(t--){

    int n,m,a,b;

    scanf("%d%d%d%d",&n,&m,&a,&b);

    printf("%lld\n",floor_sum(n,m,a,b));

  }

  

  return 0;

}