#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi,ll> pii;
typedef set <ll> si;
typedef vector <int32_t> vi32;
typedef long double ld;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define int ll
vi32 ww;
vi32 find_subset(int32_t l, int32_t u, vi32 w) {
int N = w.size();
vi ss, ss2;
vi i1(N), i2(N);
iota(all(i1), 0);
iota(all(i2),0);
int r = u;
aFOR(i,w) ww.pb(i);
sort(all(i1), [](int i,int j){
return ww[i] < ww[j];
});
sort(all(i2), [](int i,int j){
return ww[i] > ww[j];
});
sort(all(w));
ss.pb(w[0]);
FOR(i,1,N-1) ss.pb(ss.back() + w[i]);
reverse(all(w));
ss2.pb(w[0]);
FOR(i,1,N-1) ss2.pb(ss2.back() + w[i]);
//~ return vi32();
int idx = lbd(ss,l) - ss.begin();
if (idx != N && ss[idx] <= u){
vi32 ans;
FOR(i,0,idx) ans.pb(i1[i]);
return ans;
}
idx = lbd(ss2,l) - ss2.begin();
if (idx != N && ss2[idx] <= u){
vi32 ans;
//~ cout << idx << '\n';
FOR(i,0,idx) ans.pb(i2[i]);
return ans;
}
idx = ubd(ss,l) - ss.begin() - 1;
if (idx < 0) return vi32();
if (ss2[idx] < r) return vi32();
int sm = ss[idx];
multiset <pi> cur, out;
FOR(i,0,idx) cur.insert(pi(w[i], i));
FOR(i,idx+1,N-1) out.insert(pi(w[i], i));
while (sm < l){
int x = cur.begin()->f;
sm -= cur.begin()->f;
out.insert(*cur.begin());
cur.erase(cur.begin());
int y = out.rbegin()->f;
if (y < x) return vi32();
sm += out.rbegin()->f;
cur.insert(*out.rbegin());
out.erase(--out.end());
}
vi32 ans;
aFOR(i,cur) ans.pb(i.s);
return ans;
}
