## 1. Abridged problem statement

Vasya has n distinct coins with values a₁…aₙ, and needs to pay exactly x using a subset of them (no change is given). Among all subsets summing to x, find those coin denominations that appear in every such subset. Output the count and list of these "necessary" coins in any order.

---

## 2. Detailed editorial

### Goal

We want all coins that are present in every possible subset of {a₁…aₙ} whose sum is exactly x. Equivalently, a coin with value aᵢ is "non-necessary" if there exists at least one valid subset summing to x that does not include it; otherwise it is "necessary."

### Brute Force Is Too Slow

Checking for each coin i by running a fresh subset-sum DP on the other n–1 coins would cost O(n·x) per coin, for O(n²·x) total. With n up to 200 and x up to 10⁴, that can be ~4·10⁸ operations—too large.

### Prefix-Suffix DP Trick

We construct two DP tables:
- dp_pref[i][s] = whether sum s is achievable using coins a₁…aᵢ
- dp_suf[i][s] = whether sum s is achievable using coins aᵢ…aₙ

Then for coin i we ask: can we partition x into s + t = x where s is formed by some subset of coins before i (1…i–1) and t by some subset after i (i+1…n)? If yes, we can pay x without coin i, so it's non-necessary. Otherwise it's necessary.

### Implementation with Bitsets

Since x≤10⁴, we use bitset to represent a boolean array of length up to x+1.
- dp_pref[i] = dp_pref[i–1] | (dp_pref[i–1] << aᵢ)
- dp_suf[i] = dp_suf[i+1] | (dp_suf[i+1] << aᵢ)

Shift and OR propagate all sums that include coin i.

The bitset length is chosen at compile time by doubling a template parameter until it exceeds x, keeping the shifts tight.

### Answer Extraction

For each i from 1…n, check for any j in [0..x] if dp_pref[i–1][j] and dp_suf[i+1][x−j] are both true. If none such j exists, coin i is necessary.

### Time Complexity

Building both DP arrays: O(n * (x/word_size)) with bitsets. Checking each coin costs O(x). Total is O(n·x/word_size + n·x) which passes under given limits.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int MAXLEN = (int)1e4 + 42;

int n, x;
vector<int> a;

void read() {
    cin >> n >> x;
    a.resize(n);
    cin >> a;
}

template<int bit_len = 1>
void solve_with_len(int target) {
    if(target > bit_len) {
        solve_with_len<std::min(bit_len * 2, MAXLEN)>(target);
        return;
    }

    vector<bitset<bit_len>> dp_prev(n + 2);
    vector<bitset<bit_len>> dp_suff(n + 2);
    dp_prev[0][0] = 1;
    dp_suff[n + 1][0] = 1;
    for(int i = 1; i <= n; i++) {
        dp_prev[i] = dp_prev[i - 1] | (dp_prev[i - 1] << a[i - 1]);
    }

    for(int i = n; i >= 1; i--) {
        dp_suff[i] = dp_suff[i + 1] | (dp_suff[i + 1] << a[i - 1]);
    }

    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        bool ok = false;
        for(int j = 0; j <= x; j++) {
            if(dp_prev[i - 1][j] && dp_suff[i + 1][target - j]) {
                ok = true;
                break;
            }
        }

        if(!ok) {
            ans.push_back(a[i - 1]);
        }
    }

    cout << ans.size() << '\n';
    cout << ans << '\n';
}

void solve() {
    // A coin is necessary iff removing it makes paying x impossible, i.e. iff
    // no subset that sums to x uses only the other coins. dp_prev[i] is the
    // bitset of sums reachable using a prefix of the first i coins, and
    // dp_suff[i] the bitset of sums reachable using the suffix from coin i,
    // both built with subset-sum bitset shifts. Coin i can be avoided when some
    // split j + (target - j) = x is achievable with the prefix before i and the
    // suffix after i; if no such split exists the coin is necessary. The bitset
    // length is chosen at compile time by doubling a template parameter until it
    // exceeds x, keeping the shifts as tight machine-word operations.

    solve_with_len(x);
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
# Python implementation using integers as bitsets
import sys
def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    x = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    # dp_pref[i] : bitmask of achievable sums using a[0..i-1]
    dp_pref = [0] * (n + 2)
    dp_suf  = [0] * (n + 2)

    # sum=0 is always achievable
    dp_pref[0] = 1 << 0
    dp_suf[n+1] = 1 << 0

    full_mask = (1 << (x + 1)) - 1  # to trim bits > x

    # Build prefix dp
    for i in range(1, n+1):
        prev = dp_pref[i-1]
        shift = (prev << a[i-1]) & full_mask
        dp_pref[i] = prev | shift

    # Build suffix dp
    for i in range(n, 0, -1):
        nxt = dp_suf[i+1]
        shift = (nxt << a[i-1]) & full_mask
        dp_suf[i] = nxt | shift

    necessary = []
    # Check each coin
    for i in range(1, n+1):
        can_skip = False
        # Try all splits j + (x-j) = x
        pref = dp_pref[i-1]
        suf  = dp_suf[i+1]
        # Iterate j=0..x
        for j in range(x+1):
            if (pref >> j) & 1 and (suf >> (x - j)) & 1:
                can_skip = True
                break
        if not can_skip:
            necessary.append(a[i-1])

    # Output
    out = []
    out.append(str(len(necessary)))
    out.append(" ".join(map(str, necessary)))
    sys.stdout.write("\n".join(out))

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

---

## 5. Compressed editorial

Compute two bitset-based subset-sum DPs: one forward (prefix) over coins 1…i, one backward (suffix) over coins i…n. A coin i is necessary if and only if there is no split j+(x−j)=x such that sum j is reachable before i and sum x−j is reachable after i.
