#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi23_d2/debug.h"
#else
#define debug(...) void(37)
#endif
constexpr int64_t max_Y = int64_t(1E18 + 5);
int L, X;
vector<array<int64_t, 2>> answers;
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<int64_t, int>> b;
for (int i = 0; i < N; ++i) {
if (W[i] > X) {
b.emplace_back(T[i], W[i] - X);
}
}
N = int(b.size());
sort(b.begin(), b.end());
set<array<int64_t, 4>> mapping;
{
int64_t last = -1;
for (int i = 0; i <= N; ++i) {
int64_t r = (i == N ? max_Y : b[i].first);
if (last != r) {
int64_t l = last +1;
mapping.insert({l, r, l, r});
last = r;
}
}
}
for (int t = 1; t < M; ++t) {
int len = S[t] - S[t - 1];
for (int i = 0; i < N; ++i) {
b[i].first += 1LL * b[i].second * len;
}
sort(b.begin(), b.end());
int64_t mn = int64_t(4E18);
for (int i = N - 1; i >= 0; --i) {
int64_t to = b[i].first;
int64_t from = to - 1LL * b[i].second * len;
if (from >= mn) continue;
mn = from;
auto it = mapping.lower_bound(array<int64_t, 4>{from + 1, -1, -1, -1});
array<int64_t, 2> range{-1, -1};
while (it != mapping.end() && (*it)[0] <= to) {
if ((*it)[1] <= to) {
if (range[0] == -1) range[0] = (*it)[2];
range[1] = (*it)[3];
it = mapping.erase(it);
} else {
auto cur = *it;
mapping.erase(it);
if (range[0] == -1) range[0] = cur[2];
range[1] = to;
mapping.insert({to + 1, cur[1], cur[2], cur[3]});
break;
}
}
if (range[0] != -1) {
mapping.insert({to, to, range[0], range[1]});
}
}
}
for (auto[ll, rr, l, r] : mapping) {
if (ll == rr) answers.push_back({r, ll});
else answers.push_back({r, -1});
}
}
long long arrival_time(long long Y) {
int64_t ans = (*lower_bound(answers.begin(), answers.end(), array<int64_t, 2>{Y, -1}))[1];
int64_t lost = 1LL * X * L;
return (ans == -1 ? lost + Y : ans + lost);
}
