Problem: Let us compare two triples a = (xa, ya, za) and b = (xb, yb, zb) by a partial order ∠ defined as follows.
a ∠ b ⇔ xa < xb and ya < yb and za < zb



Your mission is to find, in the given set of triples, the longest ascending series a1 ∠ a2 ∠ ... ∠ ak.



Input

The input is a sequence of datasets, each specifying a set of triples formatted as follows.


m n A B
x1 y1 z1
x2 y2 z2
...
xm ym zm


Here, m, n, A and B in the first line, and all of xi, yi and zi (i = 1, . . . , m) in the following lines are non-negative integers.

Each dataset specifies a set of m + n triples. The triples p1 through pm are explicitly specified in the dataset, the i-th triple pi being (xi, yi, zi). The remaining n triples are specified by parameters A and B given to the following generator routine.


int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;
int r() {
a = 36969 * (a & M) + (a >> 16);
b = 18000 * (b & M) + (b >> 16);
return (C & ((a << 16) + b)) % 1000000;
}


Repeated 3n calls of r() defined as above yield values of xm+1, ym+1, zm+1, xm+2, ym+2, zm+2, ..., xm+n, ym+n, and zm+n, in this order.

You can assume that 1 ≤ m + n ≤ 3 × 105, 1 ≤ A,B ≤ 216, and 0 ≤ xk, yk, zk < 106 for 1 ≤ k ≤ m + n.

The input ends with a line containing four zeros. The total of m + n for all the datasets does not exceed 2 × 106.

Output

For each dataset, output the length of the longest ascending series of triples in the specified set. If pi1 ∠ pi2 ∠ ... ∠ pik is the longest, the answer should be k.

Example

Input

6 0 1 1
0 0 0
0 2 2
1 1 1
2 0 2
2 2 0
2 2 2
5 0 1 1
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
10 0 1 1
3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3
0 10 1 1
0 0 0 0


Output

3
5
1
3

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
	int LT,RT,LB,RB;
	int val;
	node(){
		LT=RT=LB=RB=-1;
		val=0;
	}
	node(int a,int b,int c,int d,int e){
		LT=a;
		RT=b;
		LB=c;
		RB=d;
		val=e;
	}
};
node pool[8000000];
int ind;
int Ret;
int nowret=0;
int query(int a,int b,int c,int d,int e,int f,int g,int h,int t){
	if(d<a||b<c)return 0;
	if(h<e||f<g)return 0;
	if(c<=a&&b<=d&&g<=e&&f<=h)return pool[t].val;
	if(nowret>=pool[t].val)return 0;
	int ret=0;
	if(~pool[t].LT){
		ret=nowret=max(ret,query(a,(a+b)/2,c,d,e,(e+f)/2,g,h,pool[t].LT));
	}
	if(~pool[t].RT){
		ret=nowret=max(ret,query(a,(a+b)/2,c,d,(e+f)/2+1,f,g,h,pool[t].RT));
	}
	if(~pool[t].LB){
		ret=nowret=max(ret,query((a+b)/2+1,b,c,d,e,(e+f)/2,g,h,pool[t].LB));
	}
	if(~pool[t].RB){
		ret=nowret=max(ret,query((a+b)/2+1,b,c,d,(e+f)/2+1,f,g,h,pool[t].RB));
	}
	return ret;
}
inline void update(int row,int col,int C){
	int now=0;
	int a=0;
	int b=1048575;
	int c=0;
	int d=1048575;
	while(1){
		pool[now].val=max(pool[now].val,C);
		if(a==b)break;
		int M=(a+b)/2;
		int N=(c+d)/2;
		if(row<=M&&col<=N){//LT
			b=M;
			d=N;
			if(~pool[now].LT){
				now=pool[now].LT;
			}else{
				pool[ind]=node();
				pool[now].LT=ind;
				now=ind++;
			}
		}
		if(row<=M&&col>N){//RT
			b=M;
			c=N+1;
			if(~pool[now].RT){
				now=pool[now].RT;
			}else{
				pool[ind]=node();
				pool[now].RT=ind;
				now=ind++;
			}
		}
		if(row>M&&col<=N){//LB
			a=M+1;
			d=N;
			if(~pool[now].LB){
				now=pool[now].LB;
			}else{
				pool[ind]=node();
				pool[now].LB=ind;
				now=ind++;
			}
		}
		if(row>M&&col>N){//RB
			a=M+1;
			c=N+1;
			if(~pool[now].RB){
				now=pool[now].RB;
			}else{
				pool[ind]=node();
				pool[now].RB=ind;
				now=ind++;
			}
		}	
	}
}
pair<int,pair<int,int> >dat[400000];
int x[400000];
int y[400000];
int z[400000];
int Q[400000];
int wolfa,wolfb,wolfC=~(1<<31),wolfM=(1<<16)-1;
int r(){
	wolfa=36969*(wolfa&wolfM)+(wolfa>>16);
	wolfb=18000*(wolfb&wolfM)+(wolfb>>16);
	return (wolfC&((wolfa<<16)+wolfb))%1000000;
}
int main(){
	int a,b,c,d;
	while(scanf("%d%d%d%d",&a,&b,&c,&d),a+b){
		for(int i=0;i<a;i++){
			scanf("%d%d%d",x+i,y+i,z+i);
			dat[i]=make_pair(x[i],make_pair(-y[i],-z[i]));
		}
		wolfa=c;
		wolfb=d;
		for(int i=0;i<b;i++){
			int X=r();
			int Y=r();
			int Z=r();
			dat[i+a]=make_pair(X,make_pair(-Y,-Z));
		}
		int n=a+b;
		std::sort(dat,dat+n);
		pool[0]=node();
		ind=1;
		Ret=0;
		for(int i=0;i<n;i++){
			nowret=0;
			int P=max(nowret,query(0,1048575,0,-dat[i].second.first-1,0,1048575,0,-dat[i].second.second-1,0))+1;
			Ret=max(Ret,P);
			Q[i]=P;
			update(-dat[i].second.first,-dat[i].second.second,P);
		}
		printf("%d\n",Ret);
	}
}