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<bits/stdc++.h>
using namespace std;
using Int = long long;
signed a , b , C = ~(1<<31), M = (1<<16)-1;
void init(signed A,signed B){a=A;b=B;}
signed r() {
  a = 36969 * (a & M) + (a >> 16);
  b = 18000 * (b & M) + (b >> 16);
  return (C & ((a << 16) + b)) % 1000000;
}

struct Point{
  Int x,y,z;
  Point(){}
  bool operator==(const Point &a)const{
    return x==a.x&&y==a.y&&z==a.z;
  }
  bool operator<(const Point &a)const{
    if(x!=a.x) return x<a.x;
    if(y!=a.y) return y>a.y;
    return z>a.z;
  }
};

signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int m,n,A,B;
  while(cin>>m>>n>>A>>B,m||n){
    init(A,B);
    
    vector<Point> ps(m+n);
    for(Int i=0;i<m;i++) cin>>ps[i].x>>ps[i].y>>ps[i].z;
    for(Int i=m;i<m+n;i++){
      ps[i].x=r();
      ps[i].y=r();
      ps[i].z=r();
    }
    n+=m;
    sort(ps.begin(),ps.end());
    using P = pair<Int, Int>;
    vector<set<P> > dp(n+1);
    
    auto print=[&](const set<P> &sp){
      for(auto p:sp) cout<<p.first<<" "<<p.second<<endl;
      cout<<endl;
    };
    
    auto veri=[&](const set<P> &sp){
      return;
      P a(-1,1e7);
      for(auto p:sp){
	assert(a.first<p.first);
	assert(a.second>p.second);
	a=p;
      }
    };
    
    auto check=[&](Int k,P p)->Int{
      if(dp[k].empty()) return 0;
      veri(dp[k]);
      auto it=dp[k].lower_bound(P(p.first,-1));
      if(it!=dp[k].begin()) --it;
      //if(it!=dp[k].begin()&&it->first>=p.first) --it;
      return it->first<p.first && it->second<p.second;
    };
    
    auto push=[&](Int k,P p){
      veri(dp[k]);
      if(dp[k].count(p)) return;
      dp[k].emplace(p);
      
      auto it=dp[k].lower_bound(p);
      while(it!=dp[k].end()){
	auto uk=it;uk++;
	if(uk==dp[k].end()) break;
	if(it->second<=uk->second){
	  dp[k].erase(uk);
	  it=dp[k].lower_bound(p);
	  continue;
	}
	break;
      }
      while(it!=dp[k].begin()){
	auto uk=it;uk--;
	if(uk->second<=it->second){
	  it=dp[k].erase(it);
	  if(it==dp[k].end()) break;
	  continue;
	}
	break;
      }
      
      veri(dp[k]);
    };
    
    for(Int i=0;i<n;i++){
      //cout<<ps[i].x<<" "<<ps[i].y<<" "<<ps[i].z<<endl;
      
      P p(ps[i].y,ps[i].z);
      Int l=0,r=i+1;
      while(l+1<r){
	Int m=(l+r)>>1;
	if(check(m,p)) l=m;
	else r=m;
      }
      push(l+1,p);
      //veri(dp[l+1]);
      
      if(0){
	cout<<l+1<<endl;
	for(int j=0;j<=n;j++){
	  cout<<j<<":"<<endl;
	  print(dp[j]);
	}
      }
    }
    
    Int ans=1;
    while(ans<n&&!dp[ans+1].empty()) ans++;
    cout<<ans<<endl;
  }
  
  return 0;
}