[1] 方針

\(N=1\) は別処理しておきます．

\(N>1\) のとき，\(X\) と \(Y=X+C(N-1)\) は異なります．

「\(X,Y\) について \(2^K\) の位が異なる」という最大の \(K\) に注目します．

イメージ図
bit:      K.......543210
X  :prefix0.............
Y  :prefix1.............

\(X\) から \(C\) ずつ加算していった際に，はじめて \(2^K\) の桁が繰り上がる瞬間に注目します．繰り上がった直後の値を \(Z\) とします． \(Z\bmod 2^K < C\) であることに注意しましょう．

イメージ図
bit:      K.......543210
X  :prefix0.............
Z  :prefix10000000suffix    suffix に C 未満の非負整数がある
Y  :prefix1.............

\(K\) および suffix を固定するごとに解く．ということを考えます．

[2] 詳細

suffix 部分の popcnt を \(p\) とすると，\(p\leq 5\) です．

\(X\) 側の選び方を考える上で重要なのは，以下の情報です．

• \(k=0,1,2,3,4,5\) について，以下をすべて満たす \(x\) の最大値．
  • \(0\leq x< 2^K\)．
  • \(x\equiv 2^K+\text{suffix}\pmod{C}\)．
  • \(\mathrm{popcnt}(x)\leq k\)．

\(Y\) 側の選び方を考える上で重要なのは，以下の情報です．

• \(k=0,1,2,3,4,5\) について，以下をすべて満たす \(y\) の最小値．
  • \(0\leq y< 2^K\)．
  • \(y\equiv \text{suffix}\pmod{C}\)．
  • \(\mathrm{popcnt}(y)\leq k\)．

これらは適当な桁 dp で計算できます（なお，クエリに共通の計算なので事前計算やメモ化などによって，同じ計算を反復することは避けられます）．

上の値が手に入っているとして，クエリに答えましょう．\(K\), suffix の場合分けを固定したときの最適解（始点 \(X\) をなるべく小さくしている状況）について考えると，\(Z-X\) としては \(O(\log C)\) 通りの候補しか考える必要がありません．上述の \(x\) が登場する境界のところ，\(X\) から \(Z\) までで \(2^K\) の位が一度しか変わらないという境界，末尾が \(Z\) になるところなどが候補となります．

それらの候補について，\(y\) 側の計算を用いれば，\(2^K\) の位以下の部分についての popcnt の最小値がとれます．よって，prefix 部分の popcnt がいくつ以上であれば条件を満たすかが分かります．それにしたがって prefix に適切な 111111 の形の値を入れれば最適解が得られます．