#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
long long off = 0;
set<pair<long long, pair<long long, long long>>> Ranges;
void init(int len, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
vector<pair<long long, int>> cur_T;
for (int i = 0; i < N; i++) {
if (W[i] > X) {
cur_T.emplace_back(T[i], W[i]);
}
}
vector<pair<long long, long long>> queries;
for (int i = 0; i < M - 1; i++) {
sort(cur_T.begin(), cur_T.end());
vector<pair<long long, int>> nxt_T(cur_T.size());
int start = 0;
long long mx = 0;
int dist = S[i + 1] - S[i];
for (int j = 0; j < (int)cur_T.size(); j++) {
if (j > 0 && cur_T[j].first != cur_T[j - 1].first) {
for (int k = start; k < j; k++) {
mx = max(mx, nxt_T[k].first);
}
start = j;
}
nxt_T[j] = {max(mx, cur_T[j].first + 1LL * cur_T[j].second * dist), cur_T[j].second};
}
for (int j = (int)cur_T.size() - 1; j >= 0; j--) {
queries.emplace_back(cur_T[j].first - off, nxt_T[j].first - off - 1LL * X * dist);
}
off += 1LL * X * dist;
cur_T.swap(nxt_T);
}
for (auto [A, B]: queries) {
A++;
B--;
if (A > B) {
continue;
}
auto it = Ranges.lower_bound({A, {-1, -1}});
if (it == Ranges.end()) {
Ranges.emplace(B + 1, make_pair(A, B));
continue;
}
long long L = min(it->second.first, A);
long long R = min(B, it->second.first - 1);
while (it->first <= B) {
R = it->second.second;
it = Ranges.erase(it);
if (it == Ranges.end()) {
R = B;
break;
}
if (R < B) {
R = min(B, it->second.first - 1);
}
}
if (L <= R) {
Ranges.emplace(B + 1, make_pair(L, R));
}
}
}
long long arrival_time(long long Y) {
long long res = Y;
for (auto [val, pos]: Ranges) {
if (pos.first <= Y && Y <= pos.second) {
res = val;
break;
}
}
res += off;
return res;
}
