#include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef vector vi; typedef vector vl; typedef long double ld; typedef unsigned long long ull; const int MAXN = 101; const int MAXH = 901; const int MAXW = 351; int n,H,W; vi h,w,ind; int totw = 0; bool last = 0; vector> DP; bitset ones; // Highest bit (from chatgpt) template int highestSetBit(const std::bitset& b) { constexpr int BITS = 64; // Iterate in 64-bit chunks from high to low for (int block = (C + BITS - 1) / BITS - 1; block >= 0; --block) { unsigned long long chunk = 0ULL; // Build this block’s bits for (int i = 0; i < BITS; ++i) { int bitIndex = block * BITS + i; if (bitIndex >= C) break; if (b.test(bitIndex)) { chunk |= (1ULL << i); } } if (chunk != 0ULL) { return block * BITS + (BITS - 1 - __builtin_clzll(chunk)); } } return -1; // none set } bool comp(int i, int j){ return h[i] < h[j]; } void answer(vi upright){ set S; cout << "upright "; trav(y, upright){ S.insert(y); cout << y+1 << " "; } cout << "\n"; cout << "stacked "; vi stacked; rep(c1,0,n){ if(S.find(c1) == S.end()){ stacked.push_back(c1); } } sort(all(stacked), comp); reverse(all(stacked)); trav(y, stacked){ cout << y+1 << " "; } cout << "\n"; return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> H >> W; bitset bs; DP.push_back(bs); rep(c1,0,n){ int a,b; cin >> a >> b; h.push_back(a); w.push_back(b); ind.push_back(c1); totw += b; bitset bs; DP.push_back(bs); } sort(all(ind), comp); int mah = h[ind.back()]; if(mah > H){ last = 1; } rep(c1,0,H+1){ ones[c1] = 1; } if(totw <= H && mah <= W){ // We must have at least one upright book, so the solution where all of them // are stacked is invalid. So if that is the only possibility, then we should // print "impossible". It is the only solution if totw<=H, max(h)<=W, and we // can't move one book to upright. int width = mah; int height = totw; vi ind; rep(c1,0,n){ ind.push_back(c1); if(width + w[c1] <= W && max(h[c1], height-w[c1]) <= H){ answer({c1}); return 0; } } // Another case, we can put a suffix upright sort(all(ind), comp); vi suff; int sumw = 0; int maxh = 0; int stack_height = totw; for(int c1 = n-1; c1 >= 1; c1--){ sumw += w[ind[c1]]; maxh = max(maxh, h[ind[c1]]); stack_height -= w[ind[c1]]; int width2 = h[ind[c1-1]] + sumw; int height2 = max(stack_height, maxh); suff.push_back(ind[c1]); if(width2 <= W && height2 <= H){ answer(suff); return 0; } } cout << "Impossible\n"; return 0; } DP[0][0] = 1; rep(c1,0,n){ int i = ind[c1]; if(h[i] > W)break; if(h[i] > H){ DP[c1+1] = (DP[c1] << w[i]); } else{ DP[c1+1] = (DP[c1] | (DP[c1] << w[i])); } if(!(last && c1 < n-1)){ bitset NEW = (DP[c1+1]&ones); int ma = highestSetBit(NEW); if(ma >= totw+h[i]-W){ int c2 = c1; vi upright; rep(c3,c1+1,n){ upright.push_back(ind[c3]); } while(c2 >= 0){ if(DP[c2][ma] && h[ind[c2]] <= H){ upright.push_back(ind[c2]); } else{ ma -= w[ind[c2]]; } c2--; } answer(upright); return 0; } } } cout << "Impossible\n"; return 0; }