#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books_sample.cpp sample_grader.cpp
// in this folder.
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(int N, int K, long long A, int S) {
// TODO implement this function
map<ll,ll>a;
vector<int>ret;
ll cur=0;
for(int i=1;i<=K;i++)a[i]=skim(i),cur+=a[i];
if(cur >= A && cur <= 2*A){
for(int i=1;i<=K;i++)ret.push_back(i);
answer(ret);
}
ll bound = N+1;
a[N+1]=3e18; //inf
for(int i=K;i>=1;i--){
cur -= a[i];
ll upper_add_limit = 2*A-cur;
auto it = a.begin();
while(it->second <= upper_add_limit)it++;
bound = min(bound,it->first); //Bound is now the index of the first exceeding known point
/*cout<<"i: "<<i<<" upper_add_limit:"<<upper_add_limit<<"\n";
cout<<"i: "<<i<<" a:";
for(auto x:a)cout<<x.first<<"->"<<x.second<<" ";
cout<<"\n";
cout<<"i: "<<i<<" bound:"<<bound<<"\n";*/
if(bound <= i+1)impossible();
it--;
ll search_left = min(bound-1,it->first);
ll search_right = bound-1; //[search_left, search_right] is the region where the last good point may be
ll best = search_left;
//cout<<"initially search_left: "<<search_left<<" search_right:"<<search_right<<"\n";
assert(it->second <= upper_add_limit);
assert(search_left >= i);
assert(search_right >= i+1);
assert(search_left <= search_right);
while(search_left < search_right){
//cout<<"search_left: "<<search_left<<" search_right:"<<search_right<<"\n";
ll mid = (search_left+search_right)/2;
ll x;
if(a.find(mid)!=a.end())x=a[mid];
else x=a[mid]=skim(mid);
if(x <= upper_add_limit){
best = search_left;
search_left = mid+1;
}
else search_right = mid-1;
}
assert(search_left == search_right);
bound = best;
cur += a[bound];
ret.push_back(bound);
if(cur >= A && cur <= 2*A){
for(int j=1;j<=i-1;j++)ret.push_back(j);
answer(ret);
}
//The hard part! The binary search
/*auto pos = upper_bound(a.begin()+i+1,a.begin()+bound,2*A-cur);
if(pos==a.begin()+i+1)impossible();
pos--;
bound = pos - a.begin();*/
}
impossible();
}
