Problem: rainovernewyork (2017 round2)

Pierre Peintre is slaving away over a new abstract painting entitled _Rain
Over New York_. This will be a simple yet powerful piece, omitting incidental
details such as busy city dwellers shielding themselves with umbrellas, and
instead focusing on the fundamental atmosphere of a rainy metropolitan day. It
will be painted on a canvas which is subdivided into a grid of 1cm x 1cm
cells, with **N** rows and **M** columns. Each cell in this grid will be
filled in with a solid color, either black, white, grey, or blue.

The lower portion of _Rain Over New York_ will depict the skyline of New York
City. In each column _i_, the bottom-most **Hi** cells will be painted grey to
represent an austere skyscraper.

Somewhere above the buildings, Pierre will place a single, innocent raincloud.
In particular, the cloud can be any rectangle of white cells on the canvas, as
long as none of them are supposed to be grey.

Below the cloud, there must be a gentle rainfall, of course. Every cell which
has a white cell somewhere directly above it and a grey cell somewhere
directly below it, and which isn't supposed to be white or grey itself, should
be painted blue. Note that there may be no such cells, if the cloud is
immediately above the skyline.

All of the remaining cells in the painting will be painted black, providing a
serene nighttime backdrop for the scene.

Pierre knows that every painting he can produce like this will sell for an
enormous sum of money, but only if it's unique. As such, he'll paint as many
different paintings as he can by varying the position and dimensions of the
raincloud depicted in them. Two paintings are considered distinct if at least
one cell on the canvas is a different color in one painting than it is in the
other.

As an example, below is an illustration of 1 of the 246 possible paintings for
the fourth sample case:

![]({{PHOTO_ID:374610330166776}})

Thanks to the incredible sum of money which Pierre is sure to make from these
works, he'll be able to purchase all of the paint that he'll need. He always
buys his paint in cans of a fixed size, each of which contains just enough to
cover a surface of 1,000,000,007 cm2, and for each color, he'll buy just
enough such cans in order to be able to complete all possible distinct
variations of his painting, once each. Always one to plan ahead, Pierre would
like to figure out exactly how much paint of each color he'll have left over
when he's done.

The sequence **H1..M** can be constructed by concatenating **K** temporary
sequences of values **S1..K**, the _i_th of which has a length of **Li**. It's
guaranteed that the sum of these sequences' lengths is equal to **M**. For
each sequence **Si**, you're given **Si,1**, and **Si,2..Li** may then be
calculated as follows, using given constants **Ai** and **Bi**:

**Si,j** = ((**Ai** * **Si,j-1** \+ **Bi**) % (**N** \- 1)) + 1 

### Input

Input begins with an integer **T**, the number of different base skylines
Pierre wants to use. For each skyline, there is first a line containing the
three space-separated integers, **N**, **M**, and **K**. Then **K** lines
follow, the _i_th of which contains the four space-separated integers **Li**,
**Si,1**, **Ai**, and **Bi**.

### Output

For the _i_th skyline, print a line containing "Case #**i**: " followed by
four space-separated integers, the total amount of black, white, grey, and
blue paint which Pierre will have left over, respectively (in cm2), after
completing all possible variations of his painting.

### Constraints

1 ≤ **T** ≤ 100  
2 ≤ **N** ≤ 1,000,000,000  
1 ≤ **M** ≤ 200,000  
1 ≤ **K** ≤ 100  
1 ≤ **Li** ≤ M  
1 ≤ **Hi**, **Si,j** ≤ **N** \- 1  
0 ≤ **Ai**, **Bi** < **N** \- 1  

### Explanation of Sample

In the first case, there's only one possible painting, with the top cell
painted white, and the remaining two cells painted grey. Pierre will buy 1 can
each of white and grey paint, and have 1,000,000,006 and 1,000,000,005 cm2
left over of those colors, respectively.

In the second case, there are 6 possible paintings: three with the cloud
covering one cell, two with the cloud covering two cells, and one with the
cloud covering three cells. Therefore, Pierre will use 10 cm2 of white paint
in total.

The fourth case corresponds to the picture shown above.



Sample input:
5
3 1 1
1 2 1 0
2 3 1
3 1 0 0
4 4 1
4 1 1 1
8 8 8
1 2 0 0
1 4 0 0
1 2 0 0
1 1 0 0
1 3 0 0
1 7 0 0
1 7 0 0
1 4 0 0
987654321 21000 6
1000 123 456 789
2000 123 789 456
3000 456 123 789
4000 456 789 123
5000 789 123 456
6000 789 456 123


Sample output:
Case #1: 0 1000000006 1000000005 0
Case #2: 999999999 999999997 999999989 0
Case #3: 999999866 999999960 999999839 999999979
Case #4: 999993978 999998905 999992627 999998774
Case #5: 298154141 32787572 172315353 565739849



Code: // Hacker Cup 2017
// Round 2
// Rain over New York
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define MOD 1000000007
#define LIM 800002

PR GCD(int a,int b)
{
		if (!b)
			return(mp(1,0));
	PR p=GCD(b,a%b);
	return(mp(p.y,p.x-p.y*(a/b)));
}

int Add(int a,int b)
{
	a+=b;
		if (a>=MOD)
			a-=MOD;
	return(a);
}

int Sub(int a,int b)
{
	a-=b;
		if (a<0)
			a+=MOD;
	return(a);
}

int Mult(int a,int b)
{
	return((LL)a*b%MOD);
}

int Div(int a,int b)
{
	b=GCD(b,MOD).x;
		if (b<0)
			b+=MOD;
	return(Mult(a,b));
}

int main()
{
	// vars
	int T,t;
	int N,M,K,L,A,B;
	int i,j,a,a2,b,b2,h,h2,h3,h4,w2,w3,sum,cnt;
	int ansB,ansW,ansG,ansR;
	set<int> S;
	set<int>::iterator I;
	static int H[LIM],D[LIM];
	static PR P[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(M),Read(K);
			M=sum=0;
				while (K--)
				{
					Read(L),Read(h),Read(A),Read(B);
						while (L--)
						{
							P[M]=mp(h,M);
							H[M++]=h;
							sum=Add(sum,h);
							h=((LL)A*h+B)%(N-1)+1;
						}
				}
			// init
			ansW=ansR=cnt=0;
			S.clear();
			S.insert(-1);
			S.insert(M);
			Fill(D,0);
			// iterate down through heights
			sort(P,P+M);
				FoxR(i,M)
				{
					// get active interval
					j=P[i].y;
					I=S.lower_bound(j);
					b=*I-j-1;
					I--;
					a=j-*I-1;
					S.insert(j);
					// clouds
					h=N-P[i].x;
					h2=Div(Mult(h,h+1),2);
					w2=Mult(a+1,b+1);
					cnt=Add(cnt,Mult(h2,w2));
					h3=Div(Mult(h,Mult(h+1,h+2)),6);
					a2=Div(Mult(a,a+1),2);
					b2=Div(Mult(b,b+1),2);
					w3=Add(w2,Add(Mult(a2,b+1),Mult(b2,a+1)));
					ansW=Add(ansW,Mult(h3,w3));
					// rain
					ansR=Add(ansR,Mult(P[i].x,Mult(h2,w3)));
					h4=Div(Mult(h-1,Mult(h,h+1)),6);
					ansR=Add(ansR,Mult(h4,w3));
					// rain to retract
					D[j-a]=Add(D[j-a],Mult(h2,b+1));
					D[j+1]=Sub(D[j+1],Mult(h2,a+b+2));
					D[j+b+2]=Add(D[j+b+2],Mult(h2,a+1));
				}
			// grey
			ansG=Mult(cnt,sum);
			// retract blue
			a=b=0;
				Fox(i,M)
				{
					a=Add(a,D[i]);
					b=Add(b,a);
					ansR=Sub(ansR,Mult(b,H[i]));
				}
			// black
			ansB=Sub(Mult(cnt,Mult(N,M)),Add(ansW,Add(ansG,ansR)));
			// output
			printf("Case #%d: %d %d %d %d\n",t,Sub(0,ansB),Sub(0,ansW),Sub(0,ansG),Sub(0,ansR));
		}
	return(0);
}