# include <stdio.h> # include <stdlib.h> # include <string.h> # include <math.h> # include <assert.h> # include <vector> # include <string> # include <queue> # include <map> # include <set> # include <iostream> # include <algorithm> # include <stack>
using namespace std;
# define foreach(it, s) for(__typedef(s.begin()) it = s.begin();it != s.end();it++) # define sgn(x) ((x)<-eps?-1:(x)>eps) typedef long long LL; typedef pair<int, int> pii;
const int maxn = 1000000 + 10; int n, num[maxn]; int ans[maxn]; pii fal[maxn], far[maxn]; int Left[maxn], Right[maxn]; const int Mod = 1000000000 + 7;
void rd(int Left, int Right, int a, int b, int c) { int len = Right - Left; long long rnum = b; for (int i=Left;i<Right;i++) { swap(num[i], num[i + rnum % len]); rnum = (rnum * a + b) % c; len--; } }
void make_data(int n, int a, int b, int c) { for (int i=0;i<n;i++) num[i] = i + 1; int Left = 0, Right = min(110, n); for (;;) { rd(Left, Right, a, b, c); Left += 100; Right += 100; if (Left >= n) break; if (Right >= n) Right = n; } }
int getfal(int r) { if (fal[r].first < 0) return r; return fal[r].first = getfal(fal[r].first); } int getfar(int r) { if (far[r].first < 0) return r; return far[r].first = getfar(far[r].first); }
int main() { int T; int cas = 0; scanf("%d", &T); while (T--) { int a, b, c; scanf("%d%d%d%d", &n, &a, &b, &c); make_data(n, a, b, c); for (int i=0;i<=n+1;i++) { fal[i] = pii(-1, i); far[i] = pii(-1, i); ans[i] = -1; Left[i] = Right[i] = 0; } int fl, fr; for (int j=n-1;j>=0;j--) { int i = num[j]; Left[i] = fal[getfal(i - 1)].second; Right[i] = far[getfar(i + 1)].second;