#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const ll inf = 1e18, maxn = 1e5 + 10;
ll a[maxn];
// --- 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.
//
void solve(int N, int k, ll A, int S) {
int l = 1, r = N;
while(l < r) {
int mid = (l + r) >> 1;
a[mid] = skim(mid);
if(a[mid] >= A) r = mid;
else l = mid + 1;
}
int pos_A = l;
if(pos_A < k) {
impossible();
return;
}
if(pos_A == k) {
ll ans = a[pos_A];
for(int i = 1; i < k; i++) a[i] = skim(i);
bool flag = false;
for(int i = 1; i < k; i++) {
ans += a[i];
if(ans > inf) {
flag = true;
break;
}
}
if(flag) {
impossible();
}
if(ans >= A && ans <= A * 2) {
vector<int> vc;
for(int i = 1; i <= k; i++) vc.push_back(i);
answer(vc);
return;
}
impossible();
return;
}
bool flag = false;
ll ans = 0;
for(int i = 1; i <= k; i++) {
a[i] = skim(i), ans += a[i];
if(ans > inf) {
flag = true;
break;
}
}
if(flag) {
impossible();
return;
}
if(ans >= A && ans <= A * 2) {
vector<int> vc;
for(int i = 1; i <= k; i++) vc.push_back(i);
answer(vc);
return;
}
if(ans > A * 2) {
impossible();
return;
}
ans -= a[k], ans += a[pos_A];
if(ans >= A && ans <= A * 2) {
vector<int> vc;
for(int i = 1; i < k; i++) vc.push_back(i);
vc.push_back(pos_A);
answer(vc);
return;
}
ans -= a[pos_A], ans += a[k];
vector<int> vc, vc2;
for(int i = k; i > 0; i--) vc.push_back(i);
for(int i = pos_A - 1; i > k && !vc.empty(); i--) {
int ind = pos_A - i;
a[i] = skim(i);
ans -= a[ind], ans += a[i];
if(ans > inf) {
impossible();
return;
}
vc.pop_back();
vc2.push_back(i);
if(ans >= A && ans <= A * 2) {
vector<int> ans_t;
for(auto j : vc) ans_t.push_back(j);
for(auto j : vc2) ans_t.push_back(j);
answer(ans_t);
return;
}
}
impossible();
}
