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 <cstring>
#include <algorithm>
using std::sort;
using std::fill;
using std::max;
using std::unique;
using std::lower_bound;
const int N = 330010;
struct point {
    int x,y,z;
    int id;
    bool operator < (const point& b) const {
        if(x == b.x) {
            if(y == b.y) return z > b.z;
            else return y > b.y;
        }
        return x < b.x;
    }
    inline void in() {
        scanf("%d%d%d",&x,&y,&z);
    }
}p[N],g[N];
int num[N];
int f[N];
inline int cmpy(point a,point b){
    return  a.y < b.y;
}
struct BIT{
    int n;
    int c[N];
    inline void init(int n) {
        this->n = n;
    }
    inline void insert(int x, int add) {
        for(; x <= n; x += x & -x) if(add > c[x]) c[x] = add;
    }
    inline int ask(int x) {
        int ret = 0;
        for(; x > 0; x -= x & -x) if(c[x] > ret) ret = c[x];
        return ret;
    }
    inline void clear(int x) {
        for(; x <= n; x += x & -x) c[x] = 0;
    }
}ta;
void update(int l1, int r1, int l2, int r2) {
    sort(g + l1, g + r1 + 1, cmpy);
    sort(g + l2, g + r2 + 1, cmpy);
    int pt = l1;
    for(int i = l2; i <= r2; i++) {
        while(pt <= r1 && g[pt].y < g[i].y){
            ta.insert(g[pt].z, f[g[pt].id]);
            pt++;
        }
        int opt=ta.ask(g[i].z - 1);
        if(opt + 1 > f[g[i].id]) {
            f[g[i].id] = opt + 1;
        }
    }
    for(int i = l1; i <= r1; i++) ta.clear(g[i].z);
}
void solve(int l,int r)
{
    if(l == r) {    
        if(1 > f[p[l].id]) f[p[l].id] = 1;
        return ; 
    }
    int mid = (l + r) >> 1;
    solve(l,mid);
    for(int i = l; i <= r; i++)    g[i] = p[i];
    if(p[mid].x != p[mid + 1].x) {
        //蟾ヲ蜿ウ蛹コ髣エ驛ス謖臥?y謗貞コ?蟾ヲ蛹コ髣エ逧з蟾イ扈丈ソ晁ッ∝ー丈コ主承蛹コ髣エ逧з莠?
        update(l, mid, mid + 1, r);
    } else {
        int leftp = mid;
        while(leftp >= l && p[leftp].x == p[mid].x) leftp--;
        int rightp = mid + 1;
        while(rightp <= r && p[rightp].x == p[mid].x) rightp++;
        if(leftp < l && rightp > r) { 
        } else if(leftp < l) {
            update(l, mid, rightp, r);
        } else if(rightp > r){
            update(l, leftp, mid + 1, r);
        } else {
            update(l, leftp, mid + 1, r);
            for(int i = l; i <= r; i++) g[i] = p[i];
            update(leftp + 1, mid, rightp, r);
        }
    }
    solve(mid+1,r);
}

int M, a, b, C;
int main()
{
    int t,m,nn,A,B;
    while(scanf("%d%d%d%d",&m,&nn,&A,&B) && (m + nn + A + B))
    {
        a = A; b = B;
        C = ~(1 << 31);
        M = (1 << 16) - 1;
        for(int i = 1; i <= m; i++) {
            p[i].in();
            p[i].id = i;
            num[i] = p[i].z;
        }
        for(int i = m + 1; i <= m + nn; i++) {
            a = 36969 * (a & M) + (a >> 16);
            b = 18000 * (b & M) + (b >> 16);
            int x = (C & ((a << 16) + b)) % 1000000;
            a = 36969 * (a & M) + (a >> 16);
            b = 18000 * (b & M) + (b >> 16);
            int y = (C & ((a << 16) + b)) % 1000000;
            a = 36969 * (a & M) + (a >> 16);
            b = 18000 * (b & M) + (b >> 16);
            int z = (C & ((a << 16) + b)) % 1000000;
            p[i].x = x;
            p[i].y = y;
            p[i].z = z;
            p[i].id = i;
            num[i] = p[i].z;
        }
        int n = m + nn;
        sort(num+1,num+n+1);
        int tot = unique(num+1,num+n+1) - num - 1; 
        for(int i = 1; i <= n; i++) p[i].z = lower_bound(num+1,num+tot+1,p[i].z) - num;
        ta.init(n);
        sort(p+1,p+n+1); 
        fill(f, f + n + 1, 1);
        solve(1, n);
        int ret = 1;
        for(int i = 1; i <= n; i++) ret = max(ret, f[i]);
        printf("%d\n",ret);
    }
    return 0;
}