#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long lld;
const int MAXN = 1e5 + 10;
const lld MOD = 1e9 + 7;
const lld INF = 1e15;

struct P{
	lld x, y;
	P(lld _x = 0, lld _y = 0) : x(_x), y(_y) {}
	bool operator < (const P& rhs) const
	{
		if(x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}
};

P p[MAXN];
vector<P> np;

bool ok(lld k, int M)
{
	int s = 1;
	int q = 0;
	int j = 0;
	for(int i = 0; i < np.size(); ++i){
		if(i < q) continue;
		j = i;
		while(j + 1 < np.size() && np[i].y <= np[j + 1].y + k){
			++j;
		}
		if(j + 1 == np.size()) break;
		for(q = j; q < np.size(); ++q){
			if(np[q].x > np[j].x + k) break;
		}
		
		if(q == np.size()) break;
		++s;
	}
	return s <= M;
}

class TheEmpireStrikesBack {
public:
	int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) {
		p[0].x = AX;
		p[0].y = AY;
		for(int i = 1; i < N; ++i){
			p[i].x = ((1LL * p[i - 1].x * BX) + CX) % MOD;
			p[i].y = ((1LL * p[i - 1].y * BY) + CY) % MOD;
		}
		sort(p, p + N);
		
		for(int i = 0; i < N; ++i){
			while(!np.empty() && np.back().x <= p[i].x && np.back().y <= p[i].y){
				np.pop_back();
			}
			np.push_back(p[i]);
		}
		
		lld l = 0;
		lld r = INF;
		while(l < r){
			lld mid = (l + r) >> 1;
			if(ok(mid, M)){
				r = mid;	
			}else{
				l = mid + 1;
			}
		}
		return l;
	}
};


<%:testing-code%>
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!