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 <cstdio>
#include <algorithm>
#include <map>
using namespace std;
#define MN 1000005
int A, B, C, M;
int rand() {
	A = 36969 * (A & M) + (A >> 16);
	B = 18000 * (B & M) + (B >> 16);
	return (C & ((A << 16) + B)) % 1000000;
}
struct data { int x, y, z, k; } d[MN];
int dyn[MN], Y;
inline bool cmp(data a, data b) {
	if (a.x != b.x) return a.x < b.x;
	if (a.y != b.y) return a.y < b.y;
	return a.z < b.z;
}
int ym[MN], yd[MN];
map <int, int> r[MN];
map<int,int>::iterator it, it2;
void upd(int x, int y, int v) {
	while (x < Y) {
		it = it2 = r[x].upper_bound(y);
		while (it2 != r[x].end() && it2->second <= v) it2++;
		r[x].erase(it, it2);
		it = r[x].upper_bound(y);
		if (it == r[x].begin() || (--it)->second < v) r[x][y] = v;
		x += x&(-x);
	}
}
int ret, val;
int f(int x, int y) {
	ret = -1;
	while (x > 0) {
		it = r[x].lower_bound(y);
		if (it != r[x].begin()) val = (--it)->second;
		else val = -1;
		if (ret < val) ret = val;
		x &= x-1;
	}
	return ret;
}
int main() {
	int i, j;
	int m, n, N;
	while (scanf("%d%d%d%d",&m,&n,&A,&B),m||n||A||B) {
		N = m+n; Y = 0;
		C = ~(1<<31); M = (1<<16)-1;
		for (i = 0; i < m; i++) scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);
		for (i = m; i < m+n; i++) d[i].x = rand(), d[i].y = rand(), d[i].z = rand();
		ym[0] = -1;
		for (i = 0; i < N; i++) d[i].k = i, ym[++Y] = d[i].y;
		sort(d, d+N, cmp);
		sort(ym+1, ym+Y+1);
		Y = 0;
		for (i = 1; i <= N; i++) if (ym[i] != ym[i-1]) yd[ym[i]] = ++Y;
		for (i = 0; i < N; i++) d[i].y = yd[d[i].y];
		Y+=2;
		for (i = 0; i < Y; i++) r[i].clear();
		i = 0;
		do {
			for (j = i; j < N && d[i].x == d[j].x; j++) dyn[d[j].k] = max(1, f(d[j].y-1, d[j].z)+1);
			for (; i < j; i++) upd(d[i].y, d[i].z, dyn[d[i].k]);
		} while (i < N);
		printf("%d\n",f(Y-1, 3*MN));
		m = n = A = B = 0;
	}
}