#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// cope counter = 2254
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

ll n, l, x;
vector<pair<ll, ll>> kms[1001];
vector<pair<ll, pair<ll, ll>>> ans;
map<ll, pair<ll, ll>> bk;

void init(int L, int N, vector<ll> t, vector<int> w, int X, int m, vector<int> S) {
	n = N, l = L, x = X;
	vector<ll> s;
	for(ll i : S) s.push_back(i);
	vector<pair<pair<ll, ll>, ll>> kk;
	ll smax;
	for(ll i = 0; i < m - 1; i++) {
		kk.clear();
		for(ll j = 0; j < n; j++) kk.push_back(mp(mp(t[j], w[j] - x), j));
		sort(kk.begin(), kk.end());
		smax = -1e18;
		for(auto j : kk) {
			smax = max(smax, j.f.f + j.f.s * (s[i + 1] - s[i]));
			kms[i + 1].push_back(mp(j.f.f, smax));
			t[j.s] = smax;
		}
	}
	map<ll, pair<ll, ll>>::iterator it;
	ll l, r;
	for(ll i = 1; i < m; i++) {
		sort(kms[i].begin(), kms[i].end(), greater<pair<ll, ll>>());
		cout << i << "\n";
		for(auto j : kms[i]) cout << j.f << " " << j.s << "\n";
		for(auto j : kms[i]) {
			if(j.f < j.s) {
				l = j.f + 1, r = j.s;
				it = bk.upper_bound(r);
				if(it != bk.end()) r = min(r, it->s.f - 1);
				while(it != bk.begin() && (--it)->f >= j.f + 1) {
					l = min(l, it->s.f);
					bk.erase(it);
					it = bk.upper_bound(r);
				}
				cout << j.s << " " << l << " " << r << "\n";
				if(l <= r) bk[j.s] = mp(l, r);
			}
		}
		cout << "\n";
	}
	for(auto i : bk) ans.push_back(mp(i.s.f, mp(i.s.s, i.f)));
}

ll arrival_time(ll y) {
	vector<pair<ll, pair<ll, ll>>>::iterator it = upper_bound(ans.begin(), ans.end(), mp(y, mp((ll)(1e18), (ll)(1e18))));
	if(it == ans.begin()) return y + x * l;
	it--;
	if(it->s.f >= y) return it->s.s + x * l;
	return y + x * l;
}