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<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<map>
using namespace std;




const int nil=0;
int func(int a,int b){
	return max(a,b);
}



class SparseRMQ{
	map<int,int> mp;
public:
	void insert(int x,int v){
		map<int,int>::iterator it,s,e;
		it=mp.lower_bound(x);
		if(it!=mp.end()&&it->first==x){
			if(v<=it->second)return;
			it->second=v;
			s=it;
			++s;
		}else if(it!=mp.begin()){
			s=it;
			if((--it)->second>=v)return;
			mp.insert(it,make_pair(x,v));
		}else{
			s=it;
			mp.insert(it,make_pair(x,v));
		}
		e=s;
		while(e!=mp.end()&&e->second<=v)++e;
		mp.erase(s,e);
	}
	int max(int xe)const{//(-inf,xe)
		map<int,int>::const_iterator it;
		it=mp.lower_bound(xe);
		if(it==mp.begin())return nil;
		return (--it)->second;
	}
};


class Dynamic2DRMQ_BIT{
	std::vector<SparseRMQ*> bit;
public:
	Dynamic2DRMQ_BIT(int xsize):bit(xsize+1,(SparseRMQ*)NULL){}
	~Dynamic2DRMQ_BIT(){
		for(int i=0;i<(int)bit.size();i++)
			if(bit[i])delete bit[i];
	}
	void insert(int x,int y,int v){
		x++;
		while(x<(int)bit.size()){
			if(!bit[x])bit[x]=new SparseRMQ();
			bit[x]->insert(y,v);
			x+= x&-x;
		}
	}
	int query(int xe,int ye)const{//[0,xe)*[0,ye)
		int res=nil;
		while(0<xe){
			if(bit[xe])res=func(res,bit[xe]->max(ye));
			xe-= xe&-xe;
		}
		return res;
	}
};




int m,n,A,B;

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

int main(){
	while(cin>>m>>n>>A>>B,m|n){
		vector<pair<int,pair<int,int> > > v(n+m),w;
		for(int i=0;i<m;i++){
			cin>>v[i].first>>v[i].second.first>>v[i].second.second;
		}
		for(int i=m;i<m+n;i++){
			v[i].first=r();
			v[i].second.first=r();
			v[i].second.second=r();
		}
		sort(v.begin(),v.end());
		int ans=0;
		Dynamic2DRMQ_BIT rmq2d(2000000);
		int prevx=-1;
		for(int i=0;i<m+n;i++){
			if(prevx<v[i].first){
				for(int j=0;j<w.size();j++)
					rmq2d.insert(w[j].second.first,w[j].second.second, w[j].first);
				w.clear();
				prevx=v[i].first;
			}
			int t=rmq2d.query(v[i].second.first,v[i].second.second)+1;
			ans=max(ans,t);
			w.push_back(make_pair(t,make_pair(v[i].second.first,v[i].second.second) ) );
		}

		cout<<ans<<endl;
	}
	return 0;
}