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 <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
int M,N,A,B,C,a,b,mod;
typedef pair<int,int> P;
typedef pair<int,P> PP;
vector< set<P> > ss;
set<P>::iterator it;
vector<PP> vc;
int ran(){
	a=36969*(a&mod)+(a>>16);
	b=18000*(b&mod)+(b>>16);
	return (C&((a<<16)+b))%1000000;
}
int main(){
	while(true){
		cin>>M>>N>>A>>B;
		if(M+N==0) break;
		ss.clear();
		vc.clear();
		a=A,b=B,C=~(1<<31),mod=(1<<16)-1;
		rep(i,M){
			int x,y,z;
			cin>>x>>y>>z;
			vc.pb(PP(x,P(-y,-z)));
		}
		rep(i,N){
			int x=ran(),y=ran(),z=ran();
			vc.pb(PP(x,P(-y,-z)));
		}
		sort(all(vc));
		N=M+N;
		rep(i,N) vc[i].sc.fs*=-1,vc[i].sc.sc*=-1;
		set<P> be;
		be.insert(P(-2,-2));
		ss.pb(be);
		int mx=0;
		rep(i,N){
			int y=vc[i].sc.fs,z=vc[i].sc.sc;
			int ub=mx+1,lb=-1;
			while(ub-lb>1){
				int m=(ub+lb)/2;
				it=ss[m].upper_bound(P(y-1,z-1));
				if(it==ss[m].begin()){
					ub=m;
					continue;
				}
				it--;
//				printf("m=%d, koko;%d,%d\n",m,it->fs,it->sc);
				if(it->sc<z) lb=m;
				else ub=m;
			}
			if(lb==-1) continue;
			int m=lb+1;
//			printf("m=%d\n",m);
			if(m>mx){
				set<P> be;
				be.insert(P(y,z));
				ss.pb(be);
				mx++;
			}else{
				it=ss[m].lower_bound(P(y,z));
				while(it!=ss[m].end()){
					if(it->sc<z) break;
//					printf("erase=(%d,%d)\n",it->fs,it->sc);
					it=ss[m].erase(it);
				}
				bool ok=true;
				it=ss[m].upper_bound(P(y,-1919));
				if(it!=ss[m].end()&&it->fs==y&&it->sc<z) ok=false;
				if(it!=ss[m].begin()){
					it--;
					if(it->sc==z) ok=false;
				}
				if(ok) ss[m].insert(P(y,z));
			}
/*			printf("i=%d,  y,z=(%d,%d)     mx=%d\n",i,y,z,mx);
			cout<<"ss[1]";
			for(auto s:ss[1]) cout<<"("<<s.fs<<","<<s.sc<<") ";
			puts("");
			if(ss.size()>2){
				cout<<"ss[2]";
				for(auto s:ss[2]) cout<<"("<<s.fs<<","<<s.sc<<") ";
				puts("");
			}*/
		}
		cout<<mx<<endl;
	}
}