#include "molecules.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
vi find_subset(int l, int u, vi w) {
int n = w.size();
vi ind(n);
iota(all(ind), 0);
sort(all(ind), [&] (int i, int j) {
return w[i] < w[j];
});
ll s = 0;
for (int x : w) s += x;
int k = n;
for (; s > u; s -= w[ind[--k]]);
if (!k) return {};
if (s >= l) {
vi v(k);
for (int i = 0; i < k; i++) v[i] = ind[i];
return v;
}
int left = k - 1, right = n - 1;
while (s < l) {
if (left < 0) return {};
s -= w[ind[left]];
left--;
if (s + w[ind[right]] < l) {
s += w[ind[right--]];
continue;
}
int begin = left, end = right, mid;
while (begin < end) {
mid = (begin + end) >> 1;
if (s + w[ind[mid]] < l) {
begin = mid + 1;
} else end = mid;
}
if (l <= s + w[ind[end]] && s + w[ind[end]] <= u) {
vi v;
for (int i = 0; i <= left; i++) v.push_back(ind[i]);
v.push_back(ind[end]);
for (int i = right + 1; i < n; i++) v.push_back(ind[i]);
return v;
}
break;
}
return {};
}
