集合あるいは数列 \(A\) に対して、\(A\) の要素の非負整数係数の線形結合として書ける数を、単に\(A\) の要素の和ということにします。特に、問題文の \(2\) つめの条件は「\(S\) は \(A\) の要素の和ではない」と表せます。

---

[1] 項数が最大の良い数列

まずは、\(A\) が項数が最大の良い数列であるという条件を整理します。

\(1\leq x \leq S\) に対して、\(A\) は \((x, S - x)\) のうちの高々一方しか含みません。また、\(S\) が偶数のときの \(S/2\) も含みません。このことから、\(\lfloor (S - 1) / 2\rfloor\) が良い数列の要素数の上界を与えることが分かります。

この上界は実現可能です。具体的には \(1\leq x\leq S-1\) かつ \(S /2< x\) となる \(x\) 全体が、項数が \(\lfloor (S-1)/2\rfloor\) の良い数列の例となります。

簡単のため、以下では項数が最大の良い数列のことを、単に「良い数列」と書くことにします。

ここまでの議論から、良い数列 \(A\) は次の性質を持つことも分かります：

• \(1\leq x < S/2\) となる \(x\) に対して、\(x, S-x\) のうちちょうど一方が \(A\) に含まれる

以下、\(1\leq x < \frac{S}{2}\) となる整数 \(x\) を下側の整数、良い数列 \(A\) に含まれる下側の整数全体を \(A\) の下側集合ということにします。良い数列は下側集合から一意に復元できるため、以下では最適な下側集合を求めることを考えていきます。

---

[2] 下側集合が満たすべき条件

良い数列の下側集合を \(X\) とします。\(X\) は次の条件を満たします。

• 条件 (a)：\(S\) は \(X\) の要素の和ではない
• 条件 (b)：\(X\) の要素の和であるような下側の整数は、再び \(X\) に属する

前者の必要性は \(A\) が良い数列という条件から明らかです。後者の性質を確認します。下側の整数 \(x\) が \(X\) の要素の和であり、\(x\notin X\) が成り立つとすると、[1] で示したことより \(S - x\) は \(A\) に含まれますが、\(S = (S-x)+x\) より \(S\) が \(A\) の要素の和となり \(A\) が良い数列であるという条件に矛盾します。

逆に、これら \(2\) 条件が十分条件であることも分かります。\(S\) が \(A\) の要素の和であったとすると、その和は高々 \(1\) 要素を除いて下側集合の要素からなることから示すことができます。

---

[3] \(O(S^2)\) 時間での解法

以上をまとめると、とりあえず \(S\) に関する多項式時間で本問題を解くことができます。

\(X = \emptyset\) から始めて、貪欲に下側集合を構成していきます。\(x = 1, 2, \ldots\) の順に、 \(X\cup \{x\}\) の要素の和で \(S\) を作ることができないならば \(X\) に \(x\) を挿入します。

この方法で、条件 (a) を満たす数列のうち辞書順最小のものが得られることは明らかです。また、このように構成した \(X\) が条件 (b) を満たすことも容易に確かめられます。

\(X\) の要素の和全体を適当な方法で管理してこれを行えば、\(O(S^2)\) などの計算量で答を求めることができます。

---

[4] 計算量の改善

下側集合 \(X\) や、その要素の和全体を上手く管理することで、計算量を改善しましょう。

\(X\) の最小要素を \(d\) と書くことにすると、条件 (b) より \(X\) は次の性質を持ちます。

• \(x \in X\) かつ \(x+d\) が下側の数ならば、\(x+d\in X\)

また \(X\) の要素の和として書ける数全体も、同様に \(d\) を加える操作で閉じています。

そこで、各 \(i\) （\(0\leq i < d\)）に対して、\(x\equiv i\pmod{d}\) となる \(X\) の最小要素 \(x\)を管理することにします。

• \(X\) に追加できる次に小さい数を探す
• \(X\) に要素を追加して、要素の和全体を更新する
• 数列の \(K\) 番目の要素を答える

といった本問を解くために必要な処理は、すべて \(d\) に関する多項式時間で行えるため、本問はテストケースごとに、\(d\) に関する多項式時間（例えば \(O(d^3)\) 時間）で解くことができます。

最適な良い数列について、\(d\) は、\(d\nmid S\) を満たす最小の正整数であることもすぐに分かります。本問の制約 \(S\leq 10^{18}\) のもと、\(d\leq 43\) であり、この計算量は十分高速です。

なお、\(\mathrm{lcm}(1, 2, \ldots, n) = \exp\bigl(n(1 + o(1))\bigr)\) より \(d = O(\log S)\) が成り立ちます。