#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct item{
ll first,second,res;
};
vector<pair<ll,ll>> arr;
vector<vector<ll>> s;
vector<vector<item>> a;
vector<vector<item>> dp;
vector<ll> station;
vector<vector<item>> temp;
ll n,x,m,mx;
bool p(item a,item b){
if(a.first==b.first) return a.second > b.second;
return a.first < b.first;
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
n=N;x=X;m=M;
mx=L;
dp.resize(m);
for(int i=0; i < n;i++){
if(W[i] > x){
arr.push_back({W[i],(ll)T[i]});
}
}
temp.resize(m);
n=arr.size();
s.resize(m);
station.resize(m);
for(int i=0; i < m;i++){
station[i]=ll(S[i]);
}
sort(arr.begin(),arr.end()); // i love alwawi he is very smart. from SAAD
reverse(arr.begin(),arr.end());
for(int i=0; i < m;i++){
s[i].resize(n);
temp[i].resize(n);
dp[i].resize(n);
}
a.resize(m);
for(int i=0; i < n;i++) s[0][i]=arr[i].second;
for(int i=1; i < m;i++){
ll length=S[i]-S[i-1];
set<pair<ll,ll>> st;
for(int j=0; j < n;j++){
ll start=s[i-1][j];
ll expected=start+(arr[j].first * length);
ll actual=expected;
auto it=st.lower_bound({start,0});
if(it!=st.begin()){
it--;
pair<ll,ll> curr=*it;
if(start > curr.first && curr.second > actual) actual=curr.second;
}
s[i][j]=actual;
st.insert({start,actual});
}
vector<item> curr(n);
for(int j=0; j < n;j++){
curr[j]={s[i-1][j],s[i][j],j};
}
sort(curr.begin(),curr.end(),p);
a[i]=curr;
}
for(int i=0; i < n;i++){
dp[m-1][i]={T[i],s[m-1][i],s[m-1][i]};
temp[m-1][i]={s[m-2][i], s[m-1][i] , s[m-1][i]};
} sort(temp[m-1].begin(),temp[m-1].end(),p);
sort(dp[m-1].begin(),dp[m-1].end(),p);
for(int i=m-2; i >=1; i--){
for(int j=0; j < n;j++){
dp[i][j]={T[j],s[i][j],dp[i+1][j].res};
temp[i][j]={s[i-1][j],s[m-1][j],0};
int l=i+1,r=m-1;
int ii=-1,jj=-1;
while(l<=r){
int mid=(l+r)/2;
int l1=0,r1=n-1;
bool ok=false;
ll length= station[mid] - station[i-1];
ll start = s[i-1][j];
ll expected = s[i-1][j] + (x * length);
while(l1<=r1){
int mid1=(l1+r1)/2;
if(start > temp[mid][mid1].first && temp[mid][mid1].second > expected){
ok=true;
ii=mid;
jj=mid1;
r1=mid1-1;
} else if (start > temp[mid][mid1].first){
l1=mid1-1;
} else{
r1=mid1-1;
}
}
if(ok) r= mid-1;
else l=mid+1;
}
if(ii!=-1){
temp[i][j].res=temp[ii][jj].res;
dp[i][j].res=temp[ii][jj].res;
} else{
ll finish=s[i][j] + ((station[m-1] - station[i]) *x);
temp[i][j].res=dp[i][j].res=finish;
}
}
sort(temp[i].begin(),temp[i].end(),p);
sort(dp[i].begin(),dp[i].end(),p);
}
}
long long arrival_time(long long Y)
{
int l=1,r=m-1;
int i=-1,j=-1;
while(l<=r){
int mid=(l+r)/2;
int l1=0,r1=n-1;
vector<item> curr=dp[mid];
ll length=station[mid];
ll expected = Y + (x*length);
bool ok=false;
while(l1 <= r1){
int mid1=(l1+r1)/2;
if(Y > curr[mid1].first && expected <= curr[mid1].second){
i=mid,j=mid1;
r1=mid1-1;
ok=true;
} else if ( curr[mid1].first > Y) r1=mid1-1;
else l1=mid1+1;
}
if(ok) r=mid-1;
else l=mid+1;
}
if(i==-1){
// cout << 1 << endl;
return (Y + (x*mx));
}
return dp[i][j].res;
}
// void solve(){
// int l,q; cin >> l >> n >> x >> m >> q;
// vector<ll> T(n);
// vector<int> W(n);
// for(int i=0; i < n;i++) cin >> T[i];
// for(int i=0; i < n;i++) cin >> W[i];
// vector<int> S(m);
// for(int i=0; i < m;i++) cin >> S[i];
// init(l,n,T,W,x,m,S);
// while(q--){
// ll temp; cin >> temp;
// cout << arrival_time(temp) << endl;
// }
// }
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// int t=1;
// // cin >> t;
// while(t--) solve();
// return 0;
// }
