//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
while (l != r) cout << (*l) << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#include "books.h"
const ll inf = 1LL<<60;
ll save[maxn];
bool found[maxn];
int tot;
ll query(int ind) {
if (ind > tot) return inf;
if (found[ind]) return save[ind];
found[ind] = 1;
return save[ind] = skim(ind);
}
void solve(int N, int K, long long A, int S) {
vector<int> ret;
tot = N;
int low = 0, up = N + 1;
ll big = 0;
while (low < up - 1) {
int mid = (low + up) / 2;
if (query(mid) >= A) up = mid, big = query(mid);
else low = mid;
}
if (up < K) {
impossible();
return;
}
//debug(up);
if (up <= N) {
ll c1 = big;
for (int i = 1;i < K;i++) c1 += query(i);
if (c1 <= 2 * A) {
for (int i = 1;i < K;i++) ret.push_back(i);
ret.push_back(up);
answer(ret);
return;
}
}
low = 0, up = min(up - K + 2, N - K + 2);
//debug(low, up);
while (up > low + 1) {
//debug(low, up);
int mid = (low + up) / 2;
ll sum = 0;
for (int i = mid;i < mid + K;i++) {
sum += query(i);
if (sum >= A) break;
}
if (sum >= A) up = mid;
else low = mid;
}
ll val = 0;
for (int i = up;i < up + K;i++) ret.push_back(i), val += query(i);
if (val >= A && val <= 2 * A) answer(ret);
else impossible();
}
/*
15 3 42 15
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 3 49 8
1 2 7 14 40 97 98 99
*/
