#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int L[1111111];
ll dp[1111111];
int par[1111111];
int leftmost[1111111];

int rt(int u)
{
	vi vec;
	while(par[u]>=0)
	{
		vec.pb(u);
		u=par[u];
	}
	for(int v:vec) par[v]=u;
	return u;
}

void merge(int u, int v)
{
	u=rt(u); v=rt(v);
	if(u==v) return ;
	if(par[u]>par[v]) swap(u,v);
	par[u]+=par[v]; par[v]=u;
	leftmost[u]=min(leftmost[u],leftmost[v]);
}

bool cmp(ii a, ii b)
{
	if(a.se!=b.se) return a.se<b.se;
	return a.fi<b.fi;
}

int lmin[1111111];
int t[4141414];

void build(vector<ii> &stones) 
{  // build the tree
	int n=stones.size();
	for(int i=n;i<2*n;i++) t[i] = stones[i-n].se;
	for (int i = n - 1; i > 0; --i) t[i] = max(t[i<<1], t[i<<1|1]);
}

void modify(int n, int p, int v) {  
  for (t[p += n] = v; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
}

int query(int n, int l, int r) {  
  int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = max(res, t[l++]);
    if (r&1) res = max(res, t[--r]);
  }
  return res;
}

map<ll,int> ma;

void add(ll x){ma[x]++;}
void del(ll x){ma[x]--; if(ma[x]==0){ma.erase(x);}}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("fossil_fuels.txt","r",stdin); freopen("fossil_fuels.out","w",stdout);
	int tc; cin>>tc;
	for(int zz=0;zz<tc;zz++)
	{
		cout<<"Case #"<<zz+1<<": ";
		int n; ll s,m; int k; cin>>n>>s>>m>>k;
		memset(par,-1,sizeof(par)); 
		for(int i=0;i<=1011111;i++) leftmost[i] = i;
		vector<ii> stones(n); int ptr1=0; int ptr2=0;
		for(int i=0;i<2*k;i++)
		{
			ll len; cin>>len;
			vector<ll> vec; ll zzz; cin>>zzz; vec.pb(zzz);
			ll x,y,z; cin>>x>>y>>z;
			for(int j=1;j<len;j++)
			{
				vec.pb(((vec.back()*x)+y)%z + 1);
				while(vec.back()<=0) vec.back()+=z;
			}
			if(i<k)
			{
				for(int j=0;j<len;j++)
				{
					stones[ptr1++].fi = vec[j];
				}
			}
			else
			{
				for(int j=0;j<len;j++)
				{
					stones[ptr2++].se = vec[j];
				}
			}
		}
		sort(stones.begin(),stones.end());
		memset(L,0,sizeof(L));
		int ptrl = 0;
		for(int i=0;i<n;i++)
		{
			while(stones[i].fi-stones[ptrl].fi>m*2) ptrl++;
			L[i] = ptrl;
		}
		vector<ii> stonesbydepth;
		for(int i=0;i<n;i++)
		{
			stonesbydepth.pb(mp(stones[i].se, i));
		}
		sort(stonesbydepth.begin(),stonesbydepth.end());
		vector<bool> used(n+2,0);
		for(ii stone:stonesbydepth)
		{
			int v=stone.se;
			used[v]=1;
			if(used[v+1]) merge(v,v+1);
			if(v>0&&used[v-1]) merge(v,v-1);
			//cerr<<"RT : "<<v<<' '<<rt(v)<<'\n';
			lmin[v] = leftmost[rt(v)];
			//cerr<<v<<' '<<lmin[v]<<'\n';
		}
		//build(1,0,n+1);
		build(stones);
		dp[0] = 0;
		ma.clear();
		deque<ii> S; S.pb(mp(0, 0)); add(0);
		//update(1,0,n+1,0,0);
		int ptr = 0;
		for(int i=1;i<=n;i++)
		{
			ll depth = stones[i-1].se; dp[i]=ll(1e18);
			/*
			ll mx=0;
			for(int j=i-1;j>=L[i-1];j--)
			{
				mx=max(mx,stones[j].se);
				dp[i] = min(dp[i], dp[j] + mx + s);
			}
			*/
			assert(query(n,lmin[i-1],i)==depth);
			while(S.size()>=2&&S[int(S.size())-2].fi>=lmin[i-1])
			{
				del(S.back().se); S.pop_back();
			}
			assert(!S.empty());
			if(S.back().fi>=lmin[i-1])
			{
				del(S.back().se);
				ll as=0;
				if(S.back().fi<i-1) 
				{
					as=query(n,S.back().fi,i-1);
					S.back().se-=as;
				}
				assert(depth>=as);
				S.back().se+=depth;
				add(S.back().se);
			}
			if(i-1>0) 
			{
				S.push_back(mp(i-1,dp[i-1]+depth)); add(dp[i-1]+depth);
			}
			while(!S.empty()&&S.front().fi<L[i-1])
			{
				int ptr=S.front().fi;
				ll tmp = S.front().se;
				S.pop_front(); del(tmp);
				ptr++;
				if(!S.empty()&&S.front().fi<=ptr) continue;
				tmp = dp[ptr] + query(n,ptr,i);
				S.push_front(mp(ptr,tmp)); add(tmp);
			}
			dp[i] = s + (*ma.begin()).fi;
			//dp[i] = query(1,0,n+1,L[i-1],i) + s;
			//update(1,0,n+1,i,dp[i]);
		}
		cout<<dp[n]<<'\n';
		cerr<<"Case #"<<zz+1<<" completed\n";
	}
}