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 <map>
#include <tuple>
#include <algorithm>

using namespace std;
typedef tuple<int, int, int> tiii;
const int INF = 1000000000;

struct Random {
	int a, b, C, M;
	Random(int A, int B) : a(A), b(B), C(~(1 << 31)), M((1 << 16) - 1) { }
	int operator()(){
		a = 36969 * (a & M) + (a >> 16);
		b = 18000 * (b & M) + (b >> 16);
		return (C & ((a << 16) + b)) % 1000000;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	while(true){
		int m, n, A, B;
		cin >> m >> n >> A >> B;
		if(m == 0 && n == 0 && A == 0 && B == 0){ break; }
		n += m;
		vector<tiii> p(n);
		for(int i = 0; i < m; ++i){
			int x, y, z;
			cin >> x >> y >> z;
			p[i] = tiii(x, y, z);
		}
		Random random(A, B);
		for(int i = m; i < n; ++i){
			const int x = random();
			const int y = random();
			const int z = random();
			p[i] = tiii(x, y, z);
		}
		sort(p.begin(), p.end());
		vector< map<int, int> > vm(n + 1);
		for(auto &v : vm){ v.insert(make_pair(-INF, INF)); }
		int answer = 0;
		for(int i = 0; i < n; ){
			const int x = get<0>(p[i]);
			vector<tiii> t;
			while(i < n && get<0>(p[i]) == x){
				const int y = get<1>(p[i]);
				const int z = get<2>(p[i]);
				int l = 0, r = n;
				while(l < r){
					const int c = l + (r - l) / 2;
					auto it = vm[c].lower_bound(y);
					if((--it)->second >= z){
						r = c;
					}else{
						l = c + 1;
					}
				}
				t.emplace_back(l, y, z);
				answer = max(answer, l + 1);
				++i;
			}
			for(const auto &e : t){
				const int k = get<0>(e);
				const int y = get<1>(e);
				const int z = get<2>(e);
				auto it = vm[k].upper_bound(y);
				--it;
				if(it->second <= z){ continue; }
				if(it->first < y){ ++it; }
				while(it != vm[k].end()){
					if(it->second < z){ break; }
					vm[k].erase(it++);
				}
				vm[k].insert(make_pair(y, z));
			}
		}
		cout << answer << endl;
	}
	return 0;
}