gistfile1.cpp

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

using namespace std;

#define MAXN 10000010

int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }

struct mq {
  int mq_a, mq_b, mq_va, mq_vb;
  int mq_v[2*MAXN];
  int mq_i[2*MAXN];

  void mq_init() {
    mq_a = mq_b = mq_va = mq_vb = 0;
  }

  void mq_push(int v) {
    while(mq_va < mq_vb && mq_v[mq_vb - 1] <= v) mq_vb--;
    mq_v[mq_vb] = v;
    mq_i[mq_vb++] = mq_b++;
  }

  void mq_pop() {
    mq_va += mq_a++ == mq_i[mq_va];
  }

  int mq_max() {
    return mq_v[mq_va];
  }
};

pair<int, long long> LO[MAXN];
pair<int, long long> HI[MAXN];

pair<int, long long> cmpmin(pair<int, long long> a, pair<int, long long> b) {
  if(b.first < a.first) return b;
  if(b.first == a.first) a.second += b.second;
  return a;
}

pair<int, long long> cmpmax(pair<int, long long> a, pair<int, long long> b) {
  if(b.first > a.first) return b;
  if(b.first == a.first) a.second += b.second;
  return a;
}

mq mnq;
mq mxq;
pair<int, long long> GMN[MAXN];
pair<int, long long> GMX[MAXN];

void compute_mnmx(vector<int>& gx, int fn, long long nm) {
  int g = gcd(fn, gx.size());
  for(int i = 0; i < g; i++) {
    vector<int> v;
    for(int j = 0; j < gx.size() / g; j++) {
      v.push_back(gx[(i + 1ll * fn * j) % gx.size()]);
    }
    if(nm >= v.size()) {
      int imn = min_element(v.begin(), v.end()) - v.begin();
      int imx = max_element(v.begin(), v.end()) - v.begin();
      for(int j = 0; j < v.size(); j++) {
        GMN[v[(v.size() + imn - j) % v.size()]] =
            make_pair(v[imn], (nm + v.size() - j - 1) / v.size());
        GMX[v[(v.size() + imx - j) % v.size()]] =
            make_pair(v[imx], (nm + v.size() - j - 1) / v.size());
      }
    } else {
      mnq.mq_init();
      mxq.mq_init();
      for(int i = 0; i < nm; i++) {
        mnq.mq_push(-v[i]);
        mxq.mq_push(v[i]);
      }
      for(int i = 0; i < v.size(); i++) {
        GMN[v[i]] = make_pair(-mnq.mq_max(), 1ll);
        GMX[v[i]] = make_pair(mxq.mq_max(), 1ll);
        mnq.mq_pop();
        mxq.mq_pop();
        mnq.mq_push(-v[(i + nm) % v.size()]);
        mxq.mq_push(v[(i + nm) % v.size()]);
      }
    }
  }
}

int main() {
  int T;
  cin >> T;
  for(int t = 1; t <= T; t++) {
    long long N;
    int P1, W1, M, K, A, B, C, D;
    cin >> N >> P1 >> W1 >> M >> K >> A >> B >> C >> D;

    for(int i = 1; i <= M; i++) {
      LO[i] = make_pair(MAXN + 1, 0ll);
      HI[i] = make_pair(-1, 0ll);
    }
    for(int i = 0; i < max(M, K) && N > 0; i++, N--) {
      LO[P1] = cmpmin(LO[P1], make_pair(W1, 1ll));
      HI[P1] = cmpmax(HI[P1], make_pair(W1, 1ll));
      P1 = (1ll * P1 * A + B) % M + 1;
      W1 = (1ll * W1 * C + D) % K + 1;
    }

    vector<int> fx(1, P1);
    vector<int> gx(1, W1);
    while(1) {
      int x = (1ll * fx.back() * A + B) % M + 1;
      if(x == fx[0]) break;
      fx.push_back(x);
    }
    while(1) {
      int x = (1ll * gx.back() * C + D) % K + 1;
      if(x == gx[0]) break;
      gx.push_back(x);
    }

    long long amt_hi = (fx.size() + N - 1) / fx.size();
    for(long long amt = amt_hi; amt >= amt_hi - 1; amt--) {
      compute_mnmx(gx, fx.size(), amt);
    
      for(int i = 0; i < N && i < fx.size(); i++) {
        long long iamt = (fx.size() + N - i - 1) / fx.size();
        if(iamt != amt) continue;
        LO[fx[i]] = cmpmin(LO[fx[i]], GMN[gx[i % gx.size()]]);
        HI[fx[i]] = cmpmax(HI[fx[i]], GMX[gx[i % gx.size()]]);
      }
    }

    long long r1 = 0, r2 = 0;
    int par = K + 1;
    for(int i = 1; i <= M; i++) {
      if(HI[i].first == -1) continue;
      if(LO[i].first < par) {
        par = LO[i].first;
        r1 += LO[i].second;
      }
    }
    par = 0;
    for(int i = M; i >= 1; i--) {
      if(HI[i].first == -1) continue;
      if(HI[i].first > par) {
        par = HI[i].first;
        r2 += HI[i].second;
      }
    }

    cout << "Case #" << t << ": " << r2 << " " << r1 << endl;
  }
  return 0;
}