#include <bits/stdc++.h>
#include "books.h"
using namespace std;
// long long ansA;
// int queries = 0;
// bool imp = false;
// vector<long long> arr;
// void answer(vector<int> a) {
// long long sum = 0;
// cout << "ANSWER = ";
// for (auto& u : a) {
// cout << u << " ";
// sum += arr[u - 1];
// }
// cout << endl;
// if (sum >= ansA && sum <= 2 * ansA) {
// cout << "OK!\n";
// } else {
// cout << "WA!\n";
// }
// }
// void impossible() {
// if (imp) cout << "OK!\n";
// else cout << "WA!\n";
// }
// long long skim(int i) {
// return arr[i - 1];
// }
bool ok(long long sum, long long A) {
return (sum >= A && sum <= A * 2);
}
void solve(int N, int K, long long A, int S) {
vector<long long> a;
long long sum = 0;
vector<int> ind;
for (int i = 1; i <= K; ++i) {
a.push_back(skim(i));
ind.push_back(i);
sum += a.back();
}
if (ok(sum, A)) {
answer(ind);
return;
}
int l = K + 1, r = N;
while (l < r) {
int m = (l + r) / 2;
long long ans = skim(m);
if (ans >= A) {
r = m;
} else {
l = m + 1;
}
}
set<int> st;
for (int i = max(K + 1, r - K); i <= r; ++i) {
ind.push_back(i);
a.push_back(skim(i));
}
sort(begin(a), end(a));
sort(begin(ind), end(ind));
a.erase(unique(begin(a), end(a)), end(a));
ind.erase(unique(begin(ind), end(ind)), end(ind));
// cout << A << ":\n";
// for (auto& u : a) {
// cout << u << " ";
// }
// cout << endl;
sum = 0;
for (int i = 0; i < K - 1; ++i) {
st.insert(ind[i]);
sum += a[i];
}
for (int j = K - 1; j < a.size(); ++j) {
sum += a[j];
st.insert(ind[j]);
if (ok(sum, A)) {
answer(vector<int>(begin(st), end(st)));
return;
}
sum -= a[j];
st.erase(ind[j]);
}
st.insert(ind[K - 1]);
sum += a[K - 1];
if (ok(sum, A)) {
answer(vector<int>(begin(st), end(st)));
return;
}
for (int i = K; i < a.size(); ++i) {
sum -= a[i - K];
st.erase(st.begin());
for (int j = i; j < a.size(); ++j) {
sum += a[j];
st.insert(ind[j]);
if (ok(sum, A)) {
answer(vector<int>(begin(st), end(st)));
return;
}
sum -= a[j];
st.erase(ind[j]);
}
sum += a[i];
st.insert(ind[i]);
}
impossible();
}
// mt19937 rng(time(NULL));
// int main() {
// ifstream cin("input.txt");
// int N, K;
// long long A;
// int S;
// cin >> N >> K >> A >> S;
// ansA = A;
// set<long long> st;
// for (; arr.size() < N;) {
// long long s;
// cin >> s;
// arr.push_back(s);
// continue;
// long long n = rng() % 100000 + 1;
// if (st.count(n)) continue;
// st.insert(n);
// arr.push_back(n);
// }
// sort(begin(arr), end(arr));
// // cout << "INITIAL = ";
// // for (auto& u : arr) {
// // cout << u << " ";
// // }
// // cout << endl;
// solve(N, K, A, S);
// }
