//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <assert.h>
using namespace std;
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 || ind < 0) 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;
while (up > low + 1) {
int mid = (low + up) / 2;
if (query(mid)>= A / K) up = mid;
else low = mid;
}
int ind = up, lef = ind, rig = ind, big = N + 1;
ll sum = 0;
if (query(ind) >= A) {
big = ind;
} else {
for (int i = 0;i < K;i++) {
ll val = query(ind + i);
if (val >= A) {
big = ind + i;
break;
}
sum += val;
rig = ind + i;
if (sum >= A) {
break;
}
}
//debug(rig, big);
while (rig - lef + 1 < K) {
lef--;
if (lef <= 0) {
lef++;
while (rig - lef + 1 < K) {
rig++;
ll val = query(rig);
sum += val;
}
break;
}
ll val = query(lef);
sum += val;
if (sum > 2 * A) sum -= query(rig), rig--;
}
if (sum >= A && sum <= 2 * A) {
for (int i = lef;i <= rig;i++) ret.push_back(i);
answer(ret);
return;
}
}
if (big > N) {
assert(query(N) < A);
impossible();
return;
} else if (big < K) {
impossible();
return;
}
sum = query(big);
ret.push_back(big);
for (int i = 1;i < K;i++) sum += query(i), ret.push_back(i);
if (sum <= 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 3 4 40 87 98 99
*/
