For a set or a sequence \(A\), we call a number that can be written as a linear combination of the elements of \(A\) with integer coefficients, simply, a sum of \(A\)’s elements. Particularly, the second condition in the statement can be stated as “\(S\) is not a sum of \(A\)’s elements.”

---

[1] A good sequence with the maximum number of terms

We begin by sorting out the condition that the number of terms in \(A\) is maximum.

For \(1\leq x \leq S\), \(A\) contains at most one of \((x, S - x)\). Neither does it contain \(S/2\) if \(S\) is even. From these facts, \(\lfloor (S - 1) / 2\rfloor\) gives an upper bound for the number of terms in a good sequence.

This upper bound is achievable. Specifically, a sequence of all \(x\) such that \(1\leq x\leq S-1\) and \(S /2< x\) is a good sequence with \(\lfloor (S-1)/2\rfloor\) terms.

For simplicity, below, we call a good sequence with the maximum number of terms simply “a good sequence.”

From the argument so far, a good sequence \(A\) also has the following property:

• For \(x\) such that \(1\leq x < S/2\), \(A\) contains exactly one of \(x\) and \(S-x\).

Below, we call an integer such that \(1\leq x < \frac{S}{2}\) low, and the set of all low integers contained in a good sequence \(A\) the low set of \(A\). Since we can uniquely restore a good sequence from its low set, we will now focus on finding the optimal low set.

---

[2] The condition to be satisfied by the low set

Let \(X\) be the low set of a good sequence \(A\). \(X\) satisfies the following conditions.

• Condition (a): \(S\) is not a sum of \(X\)’s elements.
• Condition (b): A low integer that is a sum of \(X\)’s elements again belongs to \(X\).

The necessity of the former is obvious from the condition that \(A\) is good. Let us verify the latter. If a low integer \(x\) were a sum of \(X\)’s elements and \(x\notin X\), \(A\) would contain \(S - x\) from what we show in [1]. However, since \(S = (S-x)+x\), \(S\) would be a sum of \(A\)’s elements, contradicting the condition that \(A\) is good.

On the other hand, we can also see that these two conditions are sufficient. It can be shown from the following fact: if \(S\) is a sum of \(A\)’s elements, that sum is formed of elements of the low set with at most one exception.

---

[3] A \(O(S^2)\) solution

By summing up the above, we get a solution in a time polynomial in \(S\) for the time being.

We begin with \(X = \emptyset\) and construct the low set greedily. For \(x = 1, 2, \ldots\) in this order, if \(S\) cannot be made as a sum of elements of \(X\cup \{x\}\), we insert \(x\) into \(X\).

This method obviously yields the lexicographically smallest sequence that satisfies Condition (a). It is also easy to verify that the sequence \(X\) constructed this way satisfies Condition (b).

If we do this by maintaining the set of all sums of \(X\)’s elements in some manner, the answer can be found in \(O(S^2)\) time or similar.

---

[4] Optimizing the complexity

Let us optimize the complexity by better maintaining the low set \(X\) and the set of all sums of its elements.

Let \(d\) be the smallest element in \(X\). Then, from Condition (b), \(X\) has the following property.

• If \(x \in X\) and \(x+d\) is low, \(x+d\in X\).

Similarly, the set of numbers that can be written as sums of \(X\)’s elements is also closed with respect to the addition of \(d\).

So let us maintain for each \(i\) (\(0\leq i < d\)) the smallest element \(x\) of \(X\) such that \(x\equiv i\pmod{d}\). Since the operations required to solve the problem, such as:

• look for the next smallest number that can be added to \(X\)
• add an element to \(X\) and update the set of sums of elements
• answer the \(K\)-th element of the sequence

can all be processed in a time polynomial in \(d\), we can solve the problem in a time polynomial in \(d\) (\(O(d^3)\), for example) per test case.

It is easy to see that for an optimal good sequence, \(d\) is the smallest positive integer such that \(d\nmid S\). Under the constraint \(S\leq 10^{18}\), we have \(d\leq 43\), so our solution is fast enough.

Let us remark that from \(\mathrm{lcm}(1, 2, \ldots, n) = \exp\bigl(n(1 + o(1))\bigr)\), we have \(d = O(\log S)\).