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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	Info(int arg_x,int arg_y,int arg_z){
		x = arg_x;
		y = arg_y;
		z = arg_z;
	}
	bool operator<(const struct Info &arg) const{
		if(x != arg.x){
			return x < arg.x;
		}else if(y != arg.y){
			return y > arg.y;
		}else{
			return z > arg.z;
		}
	}
	int x,y,z;
};

struct Data{
	Data(int arg_y,int arg_z){
		y = arg_y;
		z = arg_z;
	}
	bool operator<(const struct Data &arg) const{
		return y < arg.y;
	}
	int y,z;
};

int m,n,A,B;
vector<Info> V;

int a, 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;
}

void func(){

	V.clear();
	a = A;
	b = B;

	int tmp_x,tmp_y,tmp_z;

	for(int loop = 0; loop < m; loop++){

		scanf("%d %d %d",&tmp_x,&tmp_y,&tmp_z);
		V.push_back(Info(tmp_x,tmp_y,tmp_z));
	}

	for(int loop = 0; loop < n; loop++){

		tmp_x = r();
		tmp_y = r();
		tmp_z = r();

		V.push_back(Info(tmp_x,tmp_y,tmp_z));
	}

	sort(V.begin(),V.end());

	vector<set<Data>> SET(m+n);

	SET[0].insert(Data(V[0].y,V[0].z));

	int max_group = 0;
	int left,right,mid,next_group;

	for(int i = 1; i < m+n; i++){

		left = 0,right = max_group,mid = (left+right)/2;
		next_group = 0;

		while(left <= right){

			auto at = SET[mid].lower_bound(Data(V[i].y, V[i].z));

			if(at != SET[mid].begin() && (--at)->z < V[i].z){

				next_group = mid+1;
				left = mid+1;

			}else{

				right = mid-1;
			}
			mid = (left+right)/2;
		}

		if(max_group < next_group){

			max_group = next_group;
			SET[next_group].insert(Data(V[i].y,V[i].z));

		}else{

			auto at = SET[next_group].lower_bound(Data(V[i].y, V[i].z));
			while (at != SET[next_group].end() && at->z >= V[i].z){
				at = SET[next_group].erase(at);
			}

			if(SET[next_group].size() == 0){

				SET[next_group].insert(Data(V[i].y,V[i].z));

			}else{

				at = SET[next_group].lower_bound(Data(V[i].y, V[i].z));
				if(at == SET[next_group].begin() || (--at)->z != V[i].z){
					SET[next_group].insert(Data(V[i].y,V[i].z));
				}
			}
		}
	}
	printf("%d\n",max_group+1);
}

int main(){

	while(true){
		scanf("%d %d %d %d",&m,&n,&A,&B);
		if(m == 0 && n == 0 && A == 0 && B == 0)break;

		func();
	}

	return 0;
}