以下の解説では、任意の相異なる要素 \(x,y,z\) について \( y-x\neq z-y\) を満たす集合を 良い 集合と呼びます。

---

[1] 条件の言い換え

問題を解く上で重要な言い換えをします。

• 任意の相異なる要素 \(x,y,z\) について \( y-x\neq z-y \iff\) 任意の相異なる要素 \(x,y,z\) について \( 2y\neq x+z\)

この言い換えは過去のコンテストでも低難易度から高難易度にわたって何度か出ており、例えば ARC123-A で使われています。

---

[2] 総和の制約を無視した場合

以下の条件を満たす整数 \(n\) を良い整数と呼びます。

• \(n\) を \(3\) 進数で表記したとき、全ての桁が \(0\) または \(1\) である。

例えば、 \(10\) は \(3\) 進数で表記すると \(101_{(3)}\) であるため良い整数ですが、 \(7\) は \(3\) 進数で表記すると \(21_{(3)}\) であるため良い整数ではないです。

ここで、以下の性質が成立します。

• 良い整数からなる任意の集合は良い集合である。

これは非自明ですが、[1] の言い換えをした後だと簡単に証明できます。

以下 \(3\) 進数で考えます。\(y\) は良い整数なので、 \(2y\) の全ての桁は \(0\) または \(2\) です。また、\(x,z\) も良い整数なので、 \(x+z\) で繰り上がりは発生しません。以上より、\(x+z=2y\) となるのは \(x=z=y\) のときのみであることが言えます。よって示されました。

---

[3] 総和の制約を考慮する場合

良い集合の全ての要素にある整数を足したものも良い集合です。これを用いると、良い集合と \(M\) の差が \(N\) の倍数であれば、問題文で問われている集合を構築可能です。

これは、\(3\) 進数で表記したとき、下一桁が \(0\) であるような整数を順に \(N\) 個とり、下一桁を適切に調整することで得られることがわかります。

またこの方針では、\(|M|\) の制約から \(S\) の全ての要素が \(-10^7\) 以上 \(10^7\) 以下となることもわかります。

よってこの問題を解くことが出来ました。

---

[4] 実装例

Python:

n, m = map(int, input().split())
S = []
for i in range(2, 2 * n + 1, 2):
    s, tmp = 0, 1
    for j in range(15):
        if i >> j & 1:
            s += tmp
        tmp *= 3
    S.append(s)
x = (m - sum(S)) % n
for i in range(x):
    S[i] += 1
diff = (sum(S) - m) // n
print(*[s - diff for s in S])