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:
//#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <ctime>
#include <numeric>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <complex>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <string>
#include <sstream>
#include <set>
#include <stack>
#include <queue>
using namespace std;
template<class T> inline T sqr(T x) { return x * x; }
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef pair<LL, LL> PLL;
typedef pair<LL, int> PLI;
typedef pair<LD, LD> PDD;
#define MP make_pair
#define PB push_back
#define sz(x) ((int)(x).size())
#define clr(ar,val) memset(ar, val, sizeof(ar))
#define istr stringstream
#define FOR(i,n) for(int i=0;i<(n);++i)
#define forIt(mp,it) for(__typeof(mp.begin()) it = mp.begin();it!=mp.end();it++)
const double PI = acos(-1.0);

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lowbit(u) (u&(-u))

using namespace std;

int m,n,A,B,C,M;

struct Chain{
	int x,y,z,idx;
	bool operator<(const Chain& c) const{
		if(x==c.x){
			if(y==c.y) return z>c.z;
			else return y>c.y;
		}
		return x<c.x;
	}
} p[300005],pa[300005],pb[300005];

int cmp1(const Chain& c1,const Chain& c2){
	return c1.y<c2.y;
}

int r(){
	A = 36969*(A&M)+(A>>16);
	B = 18000*(B&M)+(B>>16);
	return (C&(A<<16)+B)%1000000;
}

int mx[1000005];

void add(int u,int v){
	for(int i = u;i<=1000000;i+=lowbit(i)) mx[i] = max(mx[i],v);
}

int query(int u){
	int ans = 0;
	for(int i = u;i;i-=lowbit(i)) ans = max(ans,mx[i]);
	return ans;
}

void rm(int u){
	for(int i = u;i<=1000000;i+=lowbit(i)) mx[i] = 0;
}

int ret[300005];

int solve(int l,int r){
	if(l==r) return 1;
	int mid = (l+r)>>1;
	int ans = solve(l,mid);
	int c1 = 0,c2 = 0;
	for(int i = l;i<=mid;i++) pa[c1++] = p[i];
	for(int i = mid+1;i<=r;i++) pb[c2++] = p[i];
	sort(pa,pa+c1,cmp1);
	sort(pb,pb+c2,cmp1);
	int j = 0;
	for(int i = 0;i<c2;i++){
		for(;j<c1;j++){
			if(pb[i].y<=pa[j].y) break;
			add(pa[j].z,ret[pa[j].idx]);
		}
		ret[pb[i].idx] = max(ret[pb[i].idx],query(pb[i].z-1)+1);
		ans = max(ans,ret[pb[i].idx]);
	}
	for(int j = 0;j<c1;j++) rm(pa[j].z);
	ans = max(ans,solve(mid+1,r));
	return ans;
}

int main(void){
#ifndef ONLINE_JUDGE
	//freopen("/Users/mac/Desktop/data.in","r",stdin);
#endif
	C = ~(1<<31),M = (1<<16)-1;
	while(scanf("%d %d %d %d",&m,&n,&A,&B),m+n+A+B){
		for(int i = 0;i<m;i++) scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
		for(int i = 0;i<n;i++){
			p[i+m].x = r();
			p[i+m].y = r();
			p[i+m].z = r();
		}
		n+=m;
		for(int i = 0;i<n;i++){
			p[i].idx = i,ret[i] = 1,p[i].z++;
		}
		sort(p,p+n);
		int ans = solve(0,n-1);
		printf("%d\n",ans);
	}
	return 0;
}