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:
// implement 57 min
// debug1 36min
// debug2 ?
// speed up ?
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

#include <deque>
template <class T>
ostream &operator<<(ostream &os, const vector<T> &rhs) {
  os << "[ ";
  FORIT(it, rhs) {
    if (it != rhs.begin()) { os << ", "; }
    os << *it;
  }
  os << " ]";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const deque<T> &rhs) {
  os << "[ ";
  FORIT(it, rhs) {
    if (it != rhs.begin()) { os << ", "; }
    os << *it;
  }
  os << " ]";
  return os;
}
template <class T, class U>
ostream &operator<<(ostream &os, const map<T, U> &rhs) {
  os << "{" << endl;
  FORIT(it, rhs) {
    if (it != rhs.begin()) { os << "," << endl; }
    os << "  " << it->first << " : " << it->second;
  }
  os << endl << "}";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &rhs) {
  os << "{ ";
  FORIT(it, rhs) {
    if (it != rhs.begin()) { os << ", "; }
    os << *it;
  }
  os << " }";
  return os;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
  os << "( " << rhs.first << ", " << rhs.second << " )";
  return os;
}


int m, n, A, B;
vector<int> ps[300000];
int anss[300010];
// map<pair<int, int>, int> calced;
vector<pair<pair<int, int>, int> > calced;

void generate() {
    int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;
    REP(i, n) {
        vector<int> p(3);
        REP(j, 3) {
            a = 36969 * (a & M) + (a >> 16);
            b = 18000 * (b & M) + (b >> 16);
            p[j] = (C & ((a << 16) + b)) % 1000000;
        }
        ps[m + i] = p;
    }
    n += m;
    m = n;
}

int main() {
    while (scanf("%d %d %d %d", &m, &n, &A, &B) > 0 && m + n > 0) {
        REP(i, n + m) { ps[i].clear(); }
        MEMSET(anss, -1);
        calced.clear();
        calced.push_back(make_pair(make_pair(1e+9, 1e+9), 0));
        calced.push_back(make_pair(make_pair(-1e+9, -1e+9), 0));
        REP(i, m) {
            int x, y, z;
            int v = scanf("%d %d %d", &x, &y, &z);
            assert(v == 3);
            ps[i] = { x, y, z };
        }
        generate();
        sort(ps, ps + n);
        // REP(i, n) {
        //     cout << i << " " << ps[i][1] << " " << ps[i][2] << endl;
        // }
        n = unique(ps, ps + n) - ps;
        int sqn = sqrt(n) * 1.2;
        // int sqn = 1;
        // int sqn = 10000;
        sqn = max(sqn, 1);
        int offset = 0;
        while (offset < n) {
            // calc end block
            int M = min(sqn, n - offset);
            while (offset + M < n && ps[offset + M - 1][0] == ps[offset + M][0]) { M++; }
            vector<pair<pair<int, int>, int> > ns;
            REP(i, M) {
                int pos = offset + i;
                ns.push_back(make_pair(make_pair(ps[pos][1], ps[pos][2]), offset + i));
                anss[offset + i] = 1;
            }
            sort(ns.begin(), ns.end());
            map<int, int> ts;

            // calc ans without end block
            vector<pair<int, int> > should_removed;
            auto nsit = ns.begin();
            FORIT(it, calced) {
                // cout << ts << endl;
                while (nsit != ns.end() && nsit->first.first <= it->first.first) {
                    int v = 1;
                    auto target = ts.upper_bound(-nsit->first.second);
                    if (target != ts.end()) {
                        v = target->second + 1;
                    }
                    anss[nsit->second] = v;
                    nsit++;
                }
                if (nsit == ns.end()) { break; }
                auto target = ts.end();
                while (true) {
                    target = ts.upper_bound(-it->first.second);
                    if (target == ts.end()) { break; }
                    if (target->second >= it->second) {
                        should_removed.push_back(it->first);
                        goto next;
                    }
                    if (target == ts.begin()) { break; }
                    target--;
                    if (target->second <= it->second) {
                        ts.erase(target);
                    } else if (target->first == -it->first.second) {
                        should_removed.push_back(it->first);
                        goto next;
                    } else {
                        break;
                    }
                }
                ts.insert(target, make_pair(-it->first.second, it->second));
next:;
            }
            if (should_removed.size() > 1) {
                vector<pair<pair<int, int>, int> > ncalced;
                auto it = should_removed.begin();
                REP(i, calced.size()) {
                    if (it != should_removed.end() && calced[i].first == *it) {
                        it++;
                        continue;
                    }
                    ncalced.push_back(calced[i]);
                }
                swap(calced, ncalced);
            }

            // calc ans with end block
            vector<pair<pair<int, int>, int> > tcalced;
            REP(i, M) {
                int pos = offset + i;
                REP(j, i) {
                    int ppos = offset + j;
                    if (ps[ppos][0] == ps[pos][0]) { break; }
                    if (ps[ppos][1] < ps[pos][1] && ps[ppos][2] < ps[pos][2]) {
                        anss[pos] = max(anss[pos], anss[ppos] + 1);
                    }
                }
                tcalced.push_back(make_pair(make_pair(ps[pos][1], ps[pos][2]), anss[pos]));
            }
            sort(tcalced.begin(), tcalced.end());
            // sort(calced.begin(), calced.end());
            vector<pair<pair<int, int>, int> > ncalced;
            auto it = tcalced.begin();
            REP(i, calced.size()) {
                if (it != tcalced.end() && *it <= calced[i]) {
                    ncalced.push_back(*it);
                    i--;
                    it++;
                    continue;
                }
                ncalced.push_back(calced[i]);
            }
            swap(calced, ncalced);
            // cout << calced << endl;

            offset += M;
        }
        int ans = 0;
        REP(i, n) { ans = max(ans, anss[i]); }
        printf("%d\n", ans);
    }
}