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<vector>
#include<queue>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<iostream>
#include<ctime>
#include<map>
#include<set>
using namespace std;
#define MP(x,y) make_pair((x),(y))
#define PB(x) push_back(x)
typedef long long LL;
//typedef unsigned __int64 ULL;
/* ****************** */
const int INF=100011122;
const double INFF=1e100;
const double eps=1e-8;
const LL mod=1000000007;
const int NN=300010;
const int MM=1000010;
/* ****************** */

const int limit=1000000;

int aa,bb;
int C = ~(1<<31);
int M = (1<<16)-1;
int rr() {
    aa = 36969 * (aa & M) + (aa >> 16);
    bb = 18000 * (bb & M) + (bb >> 16);
    return (C & ((aa << 16) + bb)) % 1000000;
}

struct node
{
    int x,y,z;
    bool operator<(const node &tt)const
    {
        return x<tt.x;
    }
}a[NN];
struct node1
{
    int x,y,z,id;
    bool operator<(const node1 &tt)const
    {
        if(y!=tt.y)return y<tt.y;
        return z>tt.z;
    }
}b[NN];
int dp[NN];
int c[2][limit+1];

int lowbit(int x)
{
    return x&(-x);
}
void update(int fg,int x,int val)
{
    for(;x<=limit;x+=lowbit(x))
        c[fg][x]=max(c[fg][x],val);
}
int get_max(int fg,int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x))
        ans=max(ans,c[fg][x]);
    return ans;
}
void clr_update(int fg,int x)
{
    for(;x<=limit;x+=lowbit(x))
        c[fg][x]=0;
}

void cdq(int l,int r)
{
    if(l==r)
    {
        dp[l]=max(dp[l],1);
        return;
    }
    int mid=(l+r)>>1;
    int t,i,cnt=0,tx=a[mid+1].x;

    cdq(l,mid);

    for(i=l;i<=r;i++)
    {
        b[cnt].x=a[i].x;
        b[cnt].y=a[i].y;
        b[cnt].z=a[i].z;
        b[cnt].id=i;
        cnt++;
    }
    sort(b,b+cnt);
    for(i=0;i<cnt;i++)
    {
        if(b[i].id<=mid)
        {
            update(1,b[i].z, dp[ b[i].id ] );
            if(b[i].x!=tx)
                update(0,b[i].z, dp[ b[i].id ] );
        }
        else
        {
            if(b[i].x==tx)
                t=get_max(0,b[i].z-1);
            else
                t=get_max(1,b[i].z-1);

            dp[ b[i].id ] = max( dp[ b[i].id ] , t+1 );
        }
    }
    for(i=0;i<cnt;i++)
        if(b[i].id<=mid)
        {
            clr_update(1,b[i].z);
            if(b[i].x!=tx)
                clr_update(0,b[i].z);
        }

    cdq(mid+1,r);
}

void solve(int n)
{
    int i,ans=0;
    sort(a+1,a+1+n);

    memset(c,0,sizeof(c));
    memset(dp,0,sizeof(dp));

    cdq(1,n);

    for(i=1;i<=n;i++)
        ans=max(ans,dp[i]);

    printf("%d\n",ans);
}

int main()
{
    int m,n,i;
    while(scanf("%d%d%d%d",&m,&n,&aa,&bb)!=EOF)
    {
        if(m==0 && n==0)break;

        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].x++;
            a[i].y++;
            a[i].z++;
        }
        for(i=1;i<=n;i++)
        {
            a[i+m].x=rr();
            a[i+m].y=rr();
            a[i+m].z=rr();

            a[i+m].x++;
            a[i+m].y++;
            a[i+m].z++;
        }

        solve(n+m);
    }
    return 0;
}