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 MAXN 524288
#define MAXC 1048576
#define NO_VALUE -1

#define LEFT(x) ( 2*(x) )
#define RIGHT(x) ( 2*(x)+1 )

int A, B, C, M;

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

int x[MAXN], y[MAXN], z[MAXN], ox[MAXN], val[MAXN], used[MAXC], stack[MAXN], ymap[MAXC], Y;

bool cmp_x(const int &a, const int &b) {
    if (x[a] != x[b]) return x[a] < x[b];
    else if (y[a] != y[b]) return y[a] < y[b];
    else return z[a] < z[b];
}

map<int, int> bit[MAXC];

int answer(int idx, int th) {
    map<int, int>::iterator it = bit[idx].lower_bound(th);
    if (it != bit[idx].begin()) return (--it)->second;
    else return NO_VALUE;
}

int query(int idx, int th) {
    int res = NO_VALUE;
    while (idx > 0) {
        res = max(res, answer(idx, th));
        idx &= idx-1;
    }
    return res;
}

void update(int idx, int th, int v) {
    map<int,int>::iterator it1, it2;
    while (idx < Y) {
        it1 = it2 = bit[idx].upper_bound(th);
        while (it2 != bit[idx].end() && it2->second <= v) it2++;
        bit[idx].erase(it1, it2);
    
        it1 = bit[idx].upper_bound(th);
        if (it1 == bit[idx].begin() || (--it1)->second < v) bit[idx][th] = v;
        idx += idx&(-idx);
    }
}

int main() {
    int m, n, i, j, N, t = 1, STACK;

    while (scanf("%d %d %d %d", &m, &n, &A, &B) && (m || n || A || B)) {
        C = ~(1<<31); M = (1<<16)-1;
        for (i=0; i<m; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
        for (i=m; i<m+n; i++) { x[i] = r(); y[i] = r(); z[i] = r(); }
        N = m+n;

        Y = 0;
        for (i=0; i<N; i++) {
            ox[i] = i;
            if (used[y[i]] < t) { used[y[i]] = t; stack[Y++] = y[i]; }
        }
        sort(ox, ox+N, cmp_x);
        sort(stack, stack+Y);
        for (i=0; i<Y; i++) ymap[stack[i]] = i+1;
        for (i=0; i<N; i++) y[i] = ymap[y[i]];
        t++; Y++;

        for (i=0; i<Y; i++) bit[i].clear();

        i = 0;
        do {
            for (j=i; j<N && x[ox[j]]==x[ox[i]]; j++) val[ox[j]] = max(1, query(y[ox[j]]-1, z[ox[j]])+1);
            for (; i<j; i++) update(y[ox[i]], z[ox[i]], val[ox[i]]);
        } while (i < N);
        printf("%d\n", query(Y-1, MAXC));
    }

    return 0;
}