#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mxY = 1e18;
ll X;
vector<pair<ll, ll>> ans;
vector<ll> v;
ll L;
void init(int l, int n, std::vector<long long> T, std::vector<int> W, int x, int m, std::vector<int> S) {
X = x, L = l;
vector<pair<ll, ll>> all;
for (int i = 0; i < n; i++) {
if (W[i] <= X) continue;
all.push_back({T[i], W[i] - X});
}
n = all.size();
sort(all.begin(), all.end());
set<array<ll, 4>> st;
if (n) st.insert({0, all[0].first, 0, all[0].first});
for (int i = 0; i < n; i++) {
if (i + 1 == n) {
st.insert({all[i].first + 1, mxY, all[i].first + 1, mxY});
} else {
if (all[i].first == all[i + 1].first) continue;
st.insert({all[i].first + 1, all[i + 1].first, all[i].first + 1, all[i + 1].first});
}
}
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
all[i].first += 1LL * (S[j] - S[j - 1]) * all[i].second;
if (i > 0) all[i].first = max(all[i].first, all[i - 1].first);
}
sort(all.begin(), all.end());
ll done = 2e18;
for (int i = n - 1; i >= 0; i--) {
ll point = all[i].first - 1LL * (S[j] - S[j - 1]) * all[i].second;
if (done <= point) continue;
done = point;
ll mn = 2e18, mx = -2e18;
while (true) {
auto it = st.upper_bound({point + 1, -1, -1, -1});
if (it == st.end()) break;
if ((*it)[0] > all[i].first) break;
if ((*it)[1] <= all[i].first) {
mn = min(mn, (*it)[2]);
mx = max(mx, (*it)[3]);
st.erase(it);
} else {
mn = min(mn, (*it)[2]);
mx = max(mx, all[i].first);
auto cur = *it;
st.erase(it);
st.insert({all[i].first + 1, cur[1], all[i].first + 1, cur[1]});
}
}
if (mn != 2e18) {
st.insert({all[i].first, all[i].first, mn, mx});
}
}
}
for (auto x : st) {
if (x[0] == x[1]) ans.push_back({x[2], x[3]}), v.push_back(x[0]);
}
}
long long arrival_time(long long Y) {
auto it = upper_bound(ans.begin(), ans.end(), pair<ll, ll> {Y, 2e18}) - ans.begin() - 1;
if (it < 0 || it >= ans.size()) return Y + L * X;
if (ans[it].first <= Y && Y <= ans[it].second) return v[it] + L * X;
return Y + L * X;
}
