#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int lim = 1e5 + 5;
ll cost[lim];
ll get(int i){
if(cost[i] != -1){
return cost[i];
}
return cost[i] = skim(i);
}
void solve(int n, int k, ll A, int S){
memset(cost, -1, sizeof(cost));
if(S == n){
for(int i = 1; i <= n; i++){
get(i);
}
ll pref = accumulate(cost + 1, cost + k + 1, 0LL);
if(pref > (A << 1LL)){
impossible();
return;
}
vector<int>ans;
if(pref >= A){
for(int i = 1; i <= k; i++){
ans.push_back(i);
}
answer(ans);
return;
}
ll sum = pref;
for(int i = n, j = k; i > j && j > 0; i--){
ll alt = sum - cost[j] + cost[i];
if(alt <= (A << 1LL)){
if(alt >= A){
for(int t = j - 1; t > 0; t--){
ans.push_back(t);
}
ans.push_back(i);
answer(ans);
return;
}
pref -= cost[j--];
sum = alt;
ans.push_back(i);
}
}
impossible();
return;
}
if(S >= 170){
ll pref = 0;
for(int i = 1; i <= k; i++){
pref += get(i);
}
if(pref > (A << 1LL)){
impossible();
return;
}
vector<int>ans;
if(pref >= A){
for(int i = 1; i <= k; i++){
ans.push_back(i);
}
answer(ans);
return;
}
ll sum = pref;
for(int j = k, pre = n + 1; j > 0; j--){
int low = j + 1, high = pre - 1, i = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(sum - get(j) + get(mid) <= (A << 1LL)){
low = (i = mid) + 1;
}
else{
high = mid - 1;
}
}
if(i == -1){
impossible();
return;
}
ll alt = sum - get(j) + get(i);
if(alt >= A){
for(int t = j - 1; t > 0; t--){
ans.push_back(t);
}
ans.push_back(i);
answer(ans);
return;
}
pref -= get(j);
sum = alt;
ans.push_back(pre = i);
}
impossible();
return;
}
ll pref = 0;
vector<int>ans(k);
for(int i = 1; i <= k; i++){
pref += get(ans[i - 1] = i);
}
if(pref > (A << 1LL)){
impossible();
return;
}
if(pref >= A){
answer(ans);
return;
}
int low = 1, high = n, last_small = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(get(mid) < A){
low = (last_small = mid) + 1;
}
else{
high = mid - 1;
}
}
if(last_small < n){
if(pref - get(k) + get(last_small + 1) <= (A << 1LL)){
ans[k - 1] = last_small + 1;
answer(ans);
return;
}
}
if(last_small < k){
impossible();
return;
}
for(int i = k, j = k; i > 0; i--){
ll alt = pref + get(last_small - i + 1) - get(j);
if(alt <= (A << 1LL)){
ans[--j] = last_small - i + 1;
if((pref = alt) >= A){
answer(ans);
return;
}
}
}
impossible();
}
