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 <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <random>
#include <complex>
#include <unordered_map>
#include <cmath>
#include <set>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
const int INF = 1<<28;
struct Tree {
    //using D = P;
    typedef P D;
    struct Node;
    //using NP = Node*;
    typedef Node* NP;
    static Node last_d;
    static NP last;
    struct Node {
        NP l, r;
        int sz;
        D v;
        int mn;
        Node(D v) :l(last), r(last), sz(1), v(v), mn(v.second) {}
        Node(NP l, NP r, int sz = 0) :l(l), r(r), sz(sz) {}
        void push() {

        }
        NP update() {
            sz = 1+l->sz+r->sz;
            mn = v.second;
            if (l->sz) {
                mn = min(mn, l->mn);
            }
            if (r->sz) {
                mn = min(mn, r->mn);
            }
            return this;
        }
        int lb(D a) {
            if (!sz) return 0;
            if (a <= v) return l->lb(a);
            return l->sz + 1 + r->lb(a);
        }
        int ub(D a) {
            if (!sz) return 0;
            if (v <= a) return l->sz + 1 + r->ub(a);
            return l->ub(a);
        }
        int get(int a, int b) {
            if (!sz || b <= 0 || sz <= a) return INF;
            if (a <= 0 && sz <= b) return mn;
            int res = INF;
            res = min(res, l->get(a, b));
            if (a <= l->sz && l->sz < b) res = min(res, v.second);
            res = min(res, r->get(a - l->sz - 1, b - l->sz - 1));
            return res;
        }
    } *n;

    static uint xor128(){
        static uint x=123456789,y=362436069,z=521288629,w=88675123;
        uint t;
        t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
    }
    static NP merge(NP l, NP r) {
        if (!l->sz) return r;
        if (!r->sz) return l; 
        l->push(); r->push();
        if (xor128() % (l->sz + r->sz) < l->sz) {
            l->r = merge(l->r, r);
            return l->update();
        } else {
            r->l = merge(l, r->l);
            return r->update();
        }
    }
    static pair<NP, NP> split(NP x, int k) {
        if (!x->sz) return {last, last};
        x->push();
        if (k <= x->l->sz) {
            auto y = split(x->l, k);
            x->l = y.second;
            y.second = x->update();
            return y;
        } else {
            auto y = split(x->r, k- x->l->sz -1);
            x->r = y.first;
            y.first = x->update();
            return y;
        }
    }

    Tree() : n(last) {}
    Tree(NP n) : n(n) {}
    int sz() {
        return n->sz;
    }
    void merge(Tree r) {
        n = merge(n, r.n);
    }
    Tree split(int k) {
        auto u = split(n, k);
        n = u.first;
        return Tree(u.second);
    }
    void insert(D v) {
        auto u = split(n, lb(v));
        n = merge(merge(u.first, new Node(v)), u.second);
    }
    int get(int l, int r) {
        return n->get(l, r);
    }
    int lb(D v) {
        return n->lb(v);
    }
    int ub(D v) {
        return n->ub(v);
    }
};
Tree::Node Tree::last_d = Tree::Node(NULL, NULL, 0);
Tree::NP Tree::last = &last_d;

const int MN = 303000;
int n;
int x[MN], y[MN], z[MN];
P d[MN];
T buff[MN];
Tree g[MN];

int solve() {
    for (int i = 0; i < n; i++) {
        buff[i] = T(x[i], -y[i], -z[i]);
    }
    sort(buff, buff+n);
    for (int i = 0; i < n; i++) {
        int a, b, c;
        tie(a,b,c) = buff[i];
        d[i] = P(-b, -c);
    }
    for (int i = 0; i <= n; i++) {
        g[i] = Tree();
    }
    g[0].insert(P(-1, -1));
    int res = 0;
    for (int i = 0; i < n; i++) {
        int l = 0, r = i+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (g[md].get(0, g[md].lb(P(d[i].first, -INF))) < d[i].second) {
                l = md;
            } else {
                r = md;
            }
        }
        g[r].insert(d[i]);
        res = max(res, r);
    }
    return res;
}


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;
}

int main() {
    while (true) {
        int m;
        cin >> n >> m >> a >> b;
        if (!n && !m) break;
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i] >> z[i];
        }
        for (int i = n; i < n+m; i++) {
            x[i] = r(); y[i] = r(); z[i] = r();
        }
        n += m;
        cout << solve() << endl;
    }
}