<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

421. k-th Product
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Consider n integer numbers a1, a2,..., an. Consider the products of their  m-tuples: b1, b2,..., bN. You are to find k-th largest product, i.e., k-th item in the list (bi) sorted in non-increasing order (items of the list are numbered starting from 1).

Note that the numbers can be negative.

Input
The input file contains three integer numbers n, m, k (1 ≤ n, k ≤ 10000, 1 ≤ m ≤ 13, k ≤ Cnm), followed by n integer numbers ai (-106 ≤ ai ≤ 106).

Output
Output one integer number — the k-th largest product.

Example(s)
sample input
sample output
4 3 3
2 3 3 5
30



There are four possible products in the example: 3 · 3 · 5 = 45, 2 · 3 · 5 = 30 (involving the first 3), 2 · 3 · 5 = 30 (involving the second 3), 2 · 3 · 3 = 18.

<|response|>
## 1) Abridged problem statement

Given `n` integers `a1..an` (can be negative), consider all products of choosing exactly `m` **distinct** elements (all `m`-subsets), producing `C(n,m)` products (duplicates allowed if values repeat). Sort these products in **non-increasing** order and output the **k-th** product.

Constraints: `n ≤ 10000`, `m ≤ 13`, `k ≤ 10000`, `|ai| ≤ 1e6`. Products can be very large ⇒ need big integers (or language with arbitrary precision).

---

## 2) Key observations needed to solve the problem

1. **Brute force is impossible**: `C(n,m)` is huge for `n=10000` even with small `m`.

2. **But `m ≤ 13` and `k ≤ 10000` are small**: we only need the top `k` products, not all of them.

3. **The sign depends on how many negatives are chosen**:
   - choosing an even number of negatives ⇒ product is non-negative
   - choosing an odd number of negatives ⇒ product is negative  
   So we can split the search by `x = #negatives used`, where `0 ≤ x ≤ m`.

4. **Sorting helps build “best-first” enumeration**:
   After sorting, for a fixed `x`, there is a natural “extreme” subset that is a good starting point. From it, other subsets can be reached by small local modifications (shift one chosen index by ±1 while keeping indices distinct and ordered).

5. **Best-first search over subsets**:
   Treat each chosen subset as a **state**. Push initial states into a max-heap ordered by product. Repeatedly pop the current maximum product and generate neighbor states. The `k`-th popped state gives the answer.

6. **Need to avoid duplicates**:
   Different paths of moves can reach the same subset ⇒ keep a `visited` set keyed by the selected indices.

7. **Products can exceed 64-bit**:
   - In C++ use a big integer implementation.
   - In Python use built-in `int`.

---

## 3) Full solution approach

### Step 1: Sort and split into negatives / non-negatives
Sort `a` ascending. Let `split` be the first index with `a[split] >= 0`:
- negatives: indices `[0 .. split-1]`
- non-negatives: indices `[split .. n-1]`

### Step 2: For each feasible number of negatives `x`, create an initial state
Let `x = #negatives`, `y = m - x = #non-negatives`. Feasible if `x ≤ split` and `y ≤ n-split`.

We create one initial state per feasible `x`. The provided reference solution uses:

- If `x` is **even**: start from a configuration intended to give a very large (typically non-negative) product:
  - pick `y` *largest* non-negatives (from the array end)
  - pick `x` negatives from the “other side” (as coded in the reference)

- If `x` is **odd**: product is negative, so “largest” means “closest to zero” (least negative):
  - pick `y` smallest non-negatives (closest to 0)
  - pick `x` negatives closest to 0 / strongest negatives as coded (reference picks from near `split-1`)

This gives a small set (≤ `m+1 ≤ 14`) of starting states total.

### Step 3: State representation
A state contains:
- `neg_indices`: sorted indices chosen among negatives (size `x`)
- `pos_indices`: sorted indices chosen among non-negatives (size `y`)
- boundaries (`lo/hi`) for each part so neighbor moves stay inside their segment
- cached product (bigint / Python int)

A state is uniquely identified by `(neg_indices, pos_indices)`.

### Step 4: Neighbor generation
From a state, generate neighbors by changing **one** chosen index by `±1` (the direction depends on whether the index list is increasing or decreasing in that particular construction) while:
- staying within `[lo, hi)`
- keeping indices strictly ordered (no duplicates)

Each state has at most `m` neighbors (≤ 13), so exploring ~`k` states is feasible.

### Step 5: Best-first enumeration with a priority queue
- Push all initial states into a max-heap by product.
- While popping:
  - if this is the `k`-th pop ⇒ output its product.
  - otherwise, push all unvisited neighbors.

Because we always expand the currently best product seen, the `k`-th popped product is the `k`-th largest overall (with duplicates handled naturally because different index sets are different states).

### Complexity
Let `S` be number of processed states; typically `S = O(k * m)`.
- Heap operations: `O(S log S)`
- Neighbors per pop: `O(m)`
- Product work: cached; C++ needs bigint multiplication, Python uses big ints.

With `k ≤ 10000`, `m ≤ 13`, this fits.

---

## 4) C++ implementation with detailed comments

> Note: This matches the reference approach: custom bigint + state expansion via priority queue and visited set.

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  We need big integers because (1e6)^13 doesn't fit in 64-bit.
  Below is a standard bigint implementation (base 1e9) with Karatsuba
  multiplication for speed.
*/

const int base = 1000000000;
const int base_digits = 9;

struct bigint {
    vector<int> z; // digits in base 1e9, little-endian
    int sign;      // +1 or -1

    bigint() : sign(1) {}
    bigint(long long v) { *this = v; }

    void operator=(long long v) {
        sign = 1;
        if (v < 0) sign = -1, v = -v;
        z.clear();
        while (v > 0) {
            z.push_back((int)(v % base));
            v /= base;
        }
    }

    // remove leading zeros
    void trim() {
        while (!z.empty() && z.back() == 0) z.pop_back();
        if (z.empty()) sign = 1;
    }

    bigint abs() const {
        bigint r = *this;
        r.sign = 1;
        return r;
    }

    // compare
    bool operator<(const bigint& v) const {
        if (sign != v.sign) return sign < v.sign;
        if (z.size() != v.z.size())
            return (int)z.size() * sign < (int)v.z.size() * v.sign;
        for (int i = (int)z.size() - 1; i >= 0; --i) {
            if (z[i] != v.z[i]) return z[i] * sign < v.z[i] * sign;
        }
        return false;
    }
    bool operator>(const bigint& v) const { return v < *this; }
    bool operator<=(const bigint& v) const { return !(v < *this); }
    bool operator>=(const bigint& v) const { return !(*this < v); }
    bool operator==(const bigint& v) const { return !(*this < v) && !(v < *this); }

    // unary minus
    bigint operator-() const {
        bigint r = *this;
        r.sign = -r.sign;
        return r;
    }

    // multiply by int
    void operator*=(int v) {
        if (v < 0) sign = -sign, v = -v;
        long long carry = 0;
        for (int i = 0; i < (int)z.size() || carry; ++i) {
            if (i == (int)z.size()) z.push_back(0);
            long long cur = carry + 1LL * z[i] * v;
            z[i] = (int)(cur % base);
            carry = cur / base;
        }
        trim();
    }
    bigint operator*(int v) const { bigint r = *this; r *= v; return r; }

    // helpers for karatsuba
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < (int)p.size(); i++) p[i] = p[i - 1] * 10;

        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            cur += a[i] * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back((int)(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int)cur);
        while (!res.empty() && res.back() == 0) res.pop_back();
        return res;
    }

    using vll = vector<long long>;

    static vll karatsubaMultiply(const vll& a, const vll& b) {
        int n = (int)a.size();
        vll res(n + n);
        if (n <= 32) { // schoolbook for small sizes
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return res;
        }

        int k = n / 2;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());

        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);

        for (int i = 0; i < k; i++) a2[i] += a1[i];
        for (int i = 0; i < k; i++) b2[i] += b1[i];

        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++) r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++) r[i] -= a2b2[i];

        for (int i = 0; i < (int)r.size(); i++) res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++) res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++) res[i + n] += a2b2[i];

        return res;
    }

    // bigint * bigint
    bigint operator*(const bigint& v) const {
        vector<int> a6 = convert_base(z, base_digits, 6);
        vector<int> b6 = convert_base(v.z, base_digits, 6);

        vll a(a6.begin(), a6.end());
        vll b(b6.begin(), b6.end());

        while (a.size() < b.size()) a.push_back(0);
        while (b.size() < a.size()) b.push_back(0);
        while (a.size() & (a.size() - 1)) { a.push_back(0); b.push_back(0); }

        vll c = karatsubaMultiply(a, b);

        bigint res;
        res.sign = sign * v.sign;
        long long carry = 0;
        for (int i = 0; i < (int)c.size(); i++) {
            long long cur = c[i] + carry;
            res.z.push_back((int)(cur % 1000000));
            carry = cur / 1000000;
        }
        res.z = convert_base(res.z, 6, base_digits);
        res.trim();
        return res;
    }

    void operator*=(const bigint& v) { *this = *this * v; }

    friend ostream& operator<<(ostream& os, const bigint& v) {
        if (v.sign == -1) os << '-';
        if (v.z.empty()) { os << 0; return os; }
        os << v.z.back();
        for (int i = (int)v.z.size() - 2; i >= 0; --i)
            os << setw(base_digits) << setfill('0') << v.z[i];
        return os;
    }
};

int n, m, k;
vector<int> a;

/*
  State = one chosen subset (m indices total), split into:
  - neg_indices: indices < split
  - pos_indices: indices >= split

  We store boundaries [lo, hi) for each part so we can validate moves.
  We also cache product to avoid recomputation.
*/
struct State {
    vector<int> pos_indices;
    vector<int> neg_indices;
    int pos_lo, pos_hi;
    int neg_lo, neg_hi;

    mutable bigint cached_product;
    mutable bool has_cache = false;

    State() = default;
    State(vector<int> pos, vector<int> neg, int pl, int ph, int nl, int nh)
        : pos_indices(std::move(pos)), neg_indices(std::move(neg)),
          pos_lo(pl), pos_hi(ph), neg_lo(nl), neg_hi(nh) {}

    bigint product() const {
        if (!has_cache) {
            cached_product = 1;
            for (int idx : neg_indices) cached_product *= a[idx];
            for (int idx : pos_indices) cached_product *= a[idx];
            has_cache = true;
        }
        return cached_product;
    }

    // For visited set: unique identification by chosen index vectors.
    bool operator<(const State& other) const {
        if (neg_indices != other.neg_indices) return neg_indices < other.neg_indices;
        return pos_indices < other.pos_indices;
    }
};

// Max-heap by product
struct ByProduct {
    bool operator()(const State& x, const State& y) const {
        return x.product() < y.product();
    }
};

/*
  Build an initial "extreme" state for a fixed number of negatives.
  This mirrors the reference code logic.
*/
State create_initial_state(int num_negs, int split) {
    int num_pos = m - num_negs;

    vector<int> pos(num_pos), neg(num_negs);
    int pos_lo = split, pos_hi = n;
    int neg_lo = 0, neg_hi = split;

    bool even = (num_negs % 2 == 0);

    if (even) {
        // pick largest non-negatives from the end
        for (int i = 0; i < num_pos; i++) pos[i] = n - 1 - i;
        // pick some negatives from the beginning (as in reference)
        for (int i = 0; i < num_negs; i++) neg[i] = i;
    } else {
        // pick smallest non-negatives near split
        for (int i = 0; i < num_pos; i++) pos[i] = split + i;
        // pick negatives near split-1 backwards
        for (int i = 0; i < num_negs; i++) neg[i] = split - 1 - i;
    }

    return State(pos, neg, pos_lo, pos_hi, neg_lo, neg_hi);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    int split = 0;
    while (split < n && a[split] < 0) split++;

    int total_neg = split;
    int total_pos = n - split;

    set<State> visited;
    priority_queue<State, vector<State>, ByProduct> pq;

    // Seed heap with one initial state per feasible #negatives
    for (int num_negs = 0; num_negs <= m; num_negs++) {
        int num_pos = m - num_negs;
        if (num_negs > total_neg || num_pos > total_pos) continue;

        State st = create_initial_state(num_negs, split);
        if (!visited.count(st)) {
            visited.insert(st);
            pq.push(st);
        }
    }

    // Pop the largest product states; k-th pop is answer
    for (int step = 1; step <= k; step++) {
        State cur = pq.top();
        pq.pop();

        if (step == k) {
            cout << cur.product() << "\n";
            return 0;
        }

        // Neighbor moves for pos indices
        if (!cur.pos_indices.empty()) {
            bool moving_up = (cur.pos_indices.front() < cur.pos_indices.back());
            for (int i = 0; i < (int)cur.pos_indices.size(); i++) {
                int oldv = cur.pos_indices[i];
                int newv = moving_up ? oldv + 1 : oldv - 1;

                int limit = (i + 1 < (int)cur.pos_indices.size())
                    ? cur.pos_indices[i + 1]
                    : (moving_up ? cur.pos_hi : cur.pos_lo - 1);

                bool ok = moving_up ? (newv < limit) : (newv > limit);
                if (!ok) continue;

                State nb = cur;
                nb.pos_indices[i] = newv;
                nb.has_cache = false;

                if (!visited.count(nb)) {
                    visited.insert(nb);
                    pq.push(nb);
                }
            }
        }

        // Neighbor moves for neg indices
        if (!cur.neg_indices.empty()) {
            bool moving_up = (cur.neg_indices.front() < cur.neg_indices.back());
            for (int i = 0; i < (int)cur.neg_indices.size(); i++) {
                int oldv = cur.neg_indices[i];
                int newv = moving_up ? oldv + 1 : oldv - 1;

                int limit = (i + 1 < (int)cur.neg_indices.size())
                    ? cur.neg_indices[i + 1]
                    : (moving_up ? cur.neg_hi : cur.neg_lo - 1);

                bool ok = moving_up ? (newv < limit) : (newv > limit);
                if (!ok) continue;

                State nb = cur;
                nb.neg_indices[i] = newv;
                nb.has_cache = false;

                if (!visited.count(nb)) {
                    visited.insert(nb);
                    pq.push(nb);
                }
            }
        }
    }

    return 0;
}
```

---

## 5) Python implementation with detailed comments

Python’s `int` is arbitrary precision, so the code is much shorter. We also update products incrementally (`prod // old * new`) rather than recomputing the full product every time.

```python
import sys
import heapq
from dataclasses import dataclass

@dataclass(frozen=True)
class Key:
    """Hashable key for visited states."""
    neg: tuple
    pos: tuple

class State:
    """
    A state represents one chosen subset:
      - neg_indices: chosen indices from the negative segment [0..split)
      - pos_indices: chosen indices from the non-negative segment [split..n)
    We also store the current product (Python big int).
    """
    __slots__ = ("neg_indices", "pos_indices",
                 "neg_lo", "neg_hi", "pos_lo", "pos_hi",
                 "prod")

    def __init__(self, neg_indices, pos_indices, neg_lo, neg_hi, pos_lo, pos_hi, prod):
        self.neg_indices = neg_indices
        self.pos_indices = pos_indices
        self.neg_lo = neg_lo
        self.neg_hi = neg_hi
        self.pos_lo = pos_lo
        self.pos_hi = pos_hi
        self.prod = prod

    def key(self):
        return Key(tuple(self.neg_indices), tuple(self.pos_indices))

def create_initial_state(a, n, m, split, num_negs):
    """
    Same initial-state logic as the reference code:
      even num_negs:
        - pick largest non-negatives
        - pick negatives from start
      odd num_negs:
        - pick smallest non-negatives
        - pick negatives near split-1 backwards
    """
    num_pos = m - num_negs
    even = (num_negs % 2 == 0)

    if even:
        pos_indices = [n - 1 - i for i in range(num_pos)]
        neg_indices = [i for i in range(num_negs)]
    else:
        pos_indices = [split + i for i in range(num_pos)]
        neg_indices = [split - 1 - i for i in range(num_negs)]

    prod = 1
    for idx in neg_indices:
        prod *= a[idx]
    for idx in pos_indices:
        prod *= a[idx]

    return State(neg_indices, pos_indices,
                 0, split, split, n,
                 prod)

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it)); m = int(next(it)); k = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    a.sort()

    split = 0
    while split < n and a[split] < 0:
        split += 1

    total_neg = split
    total_pos = n - split

    # max-heap via pushing (-prod, tiebreaker, state)
    heap = []
    visited = set()
    t = 0

    for num_negs in range(m + 1):
        num_pos = m - num_negs
        if num_negs > total_neg or num_pos > total_pos:
            continue
        st = create_initial_state(a, n, m, split, num_negs)
        key = st.key()
        if key not in visited:
            visited.add(key)
            heapq.heappush(heap, (-st.prod, t, st))
            t += 1

    for step in range(1, k + 1):
        negp, _, cur = heapq.heappop(heap)
        if step == k:
            print(cur.prod)
            return

        # Move one pos index by ±1 (depending on current ordering)
        if cur.pos_indices:
            moving_up = (cur.pos_indices[0] < cur.pos_indices[-1])
            for i in range(len(cur.pos_indices)):
                oldv = cur.pos_indices[i]
                newv = oldv + 1 if moving_up else oldv - 1

                if i + 1 < len(cur.pos_indices):
                    limit = cur.pos_indices[i + 1]
                else:
                    limit = cur.pos_hi if moving_up else cur.pos_lo - 1

                ok = (newv < limit) if moving_up else (newv > limit)
                if not ok:
                    continue

                pos2 = cur.pos_indices[:]
                pos2[i] = newv

                # Update product exactly (old factor divides prod because it was included)
                prod2 = cur.prod // a[oldv] * a[newv]

                nb = State(cur.neg_indices[:], pos2,
                           cur.neg_lo, cur.neg_hi, cur.pos_lo, cur.pos_hi,
                           prod2)
                key = nb.key()
                if key not in visited:
                    visited.add(key)
                    heapq.heappush(heap, (-nb.prod, t, nb))
                    t += 1

        # Move one neg index similarly
        if cur.neg_indices:
            moving_up = (cur.neg_indices[0] < cur.neg_indices[-1])
            for i in range(len(cur.neg_indices)):
                oldv = cur.neg_indices[i]
                newv = oldv + 1 if moving_up else oldv - 1

                if i + 1 < len(cur.neg_indices):
                    limit = cur.neg_indices[i + 1]
                else:
                    limit = cur.neg_hi if moving_up else cur.neg_lo - 1

                ok = (newv < limit) if moving_up else (newv > limit)
                if not ok:
                    continue

                neg2 = cur.neg_indices[:]
                neg2[i] = newv

                prod2 = cur.prod // a[oldv] * a[newv]

                nb = State(neg2, cur.pos_indices[:],
                           cur.neg_lo, cur.neg_hi, cur.pos_lo, cur.pos_hi,
                           prod2)
                key = nb.key()
                if key not in visited:
                    visited.add(key)
                    heapq.heappush(heap, (-nb.prod, t, nb))
                    t += 1

if __name__ == "__main__":
    solve()
```

---

If you want, I can also:
- explain why the “initial extreme state” choices work intuitively for each parity, or
- provide a small dry-run on the sample showing heap pops and neighbor generation.