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 <iostream>
#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], N, BEST;

bool cmp_x(const int &a, const int &b) { return x[a] < x[b]; }

map<int, int> best[MAXN];

int query(int cury, int curz) {
    int s = 0, e = N, mid;
    while (e-s > 1) {
        mid = (s+e)/2;
        map<int, int>::iterator it = best[mid].lower_bound(cury);
        if (it != best[mid].begin() && (--it)->second < curz) s = mid;
        else e = mid;
    }
    return s+1;
}

void update(int cury, int curz, int v) {
    map<int, int>::iterator it1, it2;

    BEST = max(BEST, v);

    it1 = it2 = best[v].lower_bound(cury);
    while (it2 != best[v].end() && it2->second >= curz) it2++;
    best[v].erase(it1, it2);

    it1 = best[v].upper_bound(cury);
    if (it1 == best[v].begin() || (--it1)->second > curz) best[v][cury] = curz;
}

int main() {
    int m, n, i, j;

    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;

        for (i=0; i<N; i++) ox[i] = i;
        sort(ox, ox+N, cmp_x);

        for (i=1; i<=N; i++) best[i].clear();

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

    return 0;
}