#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
//
// --- 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.
//
bool check(ll sum, ll a){
return (sum >= a && sum <= 2*a);
}
void solve(int n, int k, long long a, int s)
{
vector <ll> v(n+1, -1);
vector <int> ans;
ll sum = 0;
map <int, int> mp;
for(int i = 1; i <= k; i++){
v[i] = skim(i);
ans.push_back(i);
sum += v[i];
mp[i] = 1;
}
if(sum > 2*a){
impossible();
return;
}else if(check(sum, a)){
answer(ans);
return;
}
reverse(all(ans));
int l = k, r = n+1;
while (abs(l - r) != 1)
{
int mid = (l + r) / 2;
if(v[mid] == -1){
v[mid] = skim(mid);
}
ll tmp = sum + (v[mid] - ans[0]);
if(tmp >= sum && tmp <= 2*a)
l = mid;
else
r = mid;
}
priority_queue <pair<ll, int>> pq, px;
for(int i = 0; i < k; i++) if(l - i >= 0){
if(v[l-i] == -1){
v[l-i] = skim(l-i);
}
pq.push({ v[l-i], l-i });
}
for(auto& u : ans){
if(check(sum, a)) break;
while (!px.empty()){
pq.push(px.top());
px.pop();
}
while (!pq.empty()){
if(mp[pq.top().sd] == 1){
px.push(pq.top());
pq.pop();
}
else break;
}
if(pq.empty()) continue;
if(pq.top().fs <= v[u]) continue;
mp[u] = 0;
sum = sum + (pq.top().fs - v[u]);
u = pq.top().sd; mp[u] = 1;
pq.pop();
}
if(check(sum, a))
answer(ans);
else
impossible();
}
