\((x,y,z)\) に対して操作を \(1\) 回行った結果の \(3\) つ組を \(f(x,y,z)\) と書くことにします．操作を \(K\) 回行った結果の \(3\) つ組を \(f ^ {(K)}(x,y,z)\) と書くことにします．

\(x=y=z=0\) の場合は明らかなので，以下では \(x+y+z>0\) を仮定します．

---

[1] \(4\) 種の変換の共通点

この問題の難しさは，\(x,y,z\) の大小によって \(4\) 種の変換のどれが適用されるかが変わることです．しかし実は \(4\) 種の変換すべてに共通点があり，その共通点を見出すことが解法につながります．

まず分かりやすい性質としては，\(S := x+y+z\) が変換によって不変であることです．つまり

\[ f(x,y,z)=(x',y',z') \quad \implies \quad x+y+z=x'+y'+z' \]

が成り立ちます．次に，第 \(1\) 成分に注目します．\((x,y,z)\) を置き換えた後の第 \(1\) 成分は，

\[ x-y-z,\quad 2x,\quad y+z-x \]

のいずれかです．\(S\) を法として考えるとこれら \(3\) 種の共通点を見つけることができます．実際

\[ \begin{aligned} x-y-z&\equiv (x-y-z)+(x+y+z)\equiv 2x\pmod{S},\\ y+z-x&\equiv (y+z-x)-(x+y+z)\equiv -2x\pmod{S} \end{aligned} \]

であることから，\(S\) を法として見ると \(x\) の移り先は，\(\pm 2x\) のどちらかです．\(3\) つ組についても，\((x,y,z)\) の移り先は \(S\) を法として

\[ (2x,2y,2z),\quad (-2x,-2y,-2z) \]

のどちらかであるということが確かめられます．

---

[2] \(f^{(K)}(x,y,z)\) の計算（例外パターンを除く）

\[ a =(2^Kx)\bmod S,\quad b =(2^Ky)\bmod S,\quad c =(2^Kz)\bmod S \]

とします．\(a=0, b=0,c=0\) などが成り立つ場合は例外として，後で対処します．ここでは \(\boldsymbol{a\neq 0, b\neq 0, c\neq 0}\) であることを仮定します．

\(1\leq a,b,c < S\) と \(a+b+c\equiv 0\pmod{S}\) から，

\[ a+b+c\in \lbrace S, 2S\rbrace \]

が成り立ちます．[1] で述べた性質と，\(0\leq x,y,z\leq S\) から \( f^{(K)}(x,y,z)\) は

\[ (a,b,c),\qquad (S-a,S-b,S-c) \]

のいずれかです．このことと \(x+y+z=S\) より，

• \(a+b+c=S\) ならば \(f^{(K)}(x,y,z)=(a,b,c)\)，
• \(a+b+c=2S\) ならば \(f^{(K)}(x,y,z)=(S-a,S-b,S-c)\)

となります．

---

[3] 解法

\(2^Kx\equiv 0\pmod{S}\) になるなどの例外に対処して，解法を完成させましょう．

まず，次のことに注目します．

• \(3\) つ組 \((x,y,z)\) について，\(x,y,z\) がすべて \(2\) の倍数である場合には，すべての数を \(2\) で割ることで，\((x/2,y/2,z/2)\) に対して操作を繰り返す問題に帰着できる．つまり \(S=x+y+z\) が半分であるような問題に帰着できる．
• \(S=x+y+z\) が偶数ならば，操作を \(1\) 回行えば，\(x,y,z\) がすべて偶数である場合の問題に帰着できる．上で述べたことと合わせれば，\(S=x+y+z\) が半分であるような問題に帰着できる．

したがって，最初の \(\lfloor \log_2 S\rfloor\) 回程度の操作を先に処理してしまうことで，\(S=x+y+z\) が奇数の場合の問題に帰着できます．

\(S=x+y+z\) が奇数であるとき，\(2^Kx\equiv 0\pmod{S}\) となるのは \(x\equiv 0\) となる場合に限られます．したがって，

1. \(x, y, z\) がどれも \(0\) でない場合：[2] で述べた例外は起こらない．
2. \(x,y,z\) のうちちょうどひとつが \(0\) である場合．例えば \(x=0,y\neq 0,z\neq 0\) とする．このとき操作によって \((0,y,z)\) は必ず \((0,2y\bmod S,2z\bmod S)\) にうつることが確かめられる．
3. \(x,y,z\) のうちちょうどふたつが \(0\) である場合．例えば \((x,y,z)=(0,0,S)\) であるとする．操作によって \((0,0,S)\) は \((0,0,S)\) のままであることが確かめられる．

となります．

3 番目の場合答えの計算は容易です．

2 番目の場合は

\[ a =(2^Kx)\bmod S,\quad b =(2^Ky)\bmod S,\quad c =(2^Kz)\bmod S \]

とすれば \(a=0,b+c=S\) が成り立ち，また \(f^{(K)}(x,y,z)=(a,b,c)\) が成り立つため，1 番目の場合と同じ規則で \(f^{(K)}(x,y,z)\) を扱えます．

本問では \(f^{(K)}(A_1,A_2,A_3)=(B_1,B_2,B_3)\) となる \(K\) を求めることが課題です．上のような前処理を行えば，この問題は

\[ \begin{aligned} 2^KA_1&\equiv b_1\pmod{S},\\ 2^KA_2&\equiv b_2\pmod{S},\\ 2^KA_3&\equiv b_3\pmod{S} \end{aligned} \]

というタイプの \(3\) つの式を同時に満たす \(K\) を求める問題として言い換えることができます（\((b_1,b_2,b_3)=(B_1,B_2,B_3)\) や \((S-B_1,S-B_2,S-B_3)\) などに対して解くというようにすればよいです）．これは離散対数問題という有名問題の変種です．

---

[4] 本問の離散対数問題の解き方

BSGS（Baby Step Giant Step）と呼ばれる解法が本問にも適用可能です（初見の方は，ABC270G や ARC042D なども参照してください）．

\(S\) が奇数の場合に帰着されているため，\(2\) は \(S\) を法として乗法逆元を持つことに注意してください．

適当な \(L\) をとり，\(K=iL+j\) と表します．

\[ \begin{aligned} 2^KA_1&\equiv b_1\pmod{S},\\ 2^KA_2&\equiv b_2\pmod{S},\\ 2^KA_3&\equiv b_3\pmod{S} \end{aligned} \]

は

\[ \begin{aligned} 2^{j}A_1&\equiv 2^{-Li}b_1\pmod{S},\\ 2^{j}A_2&\equiv 2^{-Li}b_2\pmod{S},\\ 2^{j}A_3&\equiv 2^{-Li}b_3\pmod{S} \end{aligned} \]

と同値です．まず \(j=0,1,\ldots,L\) に対して

\[ (2^{j}A_1\bmod S,2^{j}A_2\bmod S,2^{j}A_3\bmod S) \]

を計算しておきます．次に \(i=0,1,\ldots,L\) に対して

\[ (2^{-Li}b_1\bmod S,2^{-Li}b_2\bmod S,2^{-Li}b_3\bmod S) \]

を計算しながら組 \((i,j)\) を探すようにします．調べる \(K\) の上限を \(K_{\max}\) として \(L=\sqrt{K_{\max}}\) とすることで，\(O(\sqrt{K_{\max}}\log K_{\max})\) などの計算量で，最小の解 \(K\) を求めることができます．また，\(2^k\bmod S\) は高々 \(S\) 通りなので，\(K_{\max}\) は \(S\) にとることができます．

なお上の解法では \(2\) が乗法逆元を持つことを用いましたが，より弱い仮定で（例えば \(S\) が偶数であるとしたまま）この問題を解くことも可能です．そのような解法は モノイド作用に関する離散対数問題 を参考にしてください．