There are n boxes. Boxes contain marbles.
Box number 1 contains 1 marble.
Box number 2 contains 2 marbles.
...
Box number n contains n marbles.

We have to choose exactly b boxes out of n original boxes, so that we would have exactly t marbles in total.

For example, if we have a set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 4 boxes to get the total target value t = 13, then we should output 1 3 4 5.

But if we have the same set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 3 boxes with the same total value of t = 13, then we have to print Impossible.

I have a simple bruteforce solution, which is working, but for too long. And I have a dynamic programming solution, which is not correct:

long long dp[10000][100];

for (int v = 1; v <= n; v++) dp[v][1] = 1ll << v;

for (int boxes = 2; boxes <= b; boxes++)
  for (int cur = 1; cur <= t; cur++)
    for (int v = 1; v <= n; v++)
      if (cur - v >= 1)
      {
        long long flag = dp[cur - v][boxes - 1] & (1ll << v);
        long long possible = dp[cur - v][boxes - 1];
        if (!flag && possible)
          dp[cur][boxes] = dp[cur - v][boxes - 1] | (1ll << v);
      }

My dp solution is not correct, because it remembers only one configuration. For example, to get target value t = 5, we can choose (1, 4) or we can choose (2, 3). My code will remember only one of those 2 choices.

The task becomes even more complicated when we a given the following constraints:
1 ≤ n ≤ 10¹⁸
1 ≤ t ≤ 10⁶
1 ≤ b ≤ n