\((X, Y)\) の列の代わりに，\((a:=X+3Y, b:=3X+Y)\) の列を考えてみましょう．この列の \(a, b\) が互いに異なれば良いです．

まず，\(a\) は \(4 \leq a \leq N + 3M\) を満たします．各 \(a\) に対して \(b\) の候補を考えます．

\(X+3Y=a, 3X+Y=b\) より\(X = (3b-a)/8, Y=(3a-b)/8\) です．\(X, Y\) の整数性より \( b = 3a \bmod 8, a = 3b \bmod 8\) が必要ですが，一方が成り立てばもう片方も成り立ちます．

よって，\((a, b)\) に対してその値をとる \((X, Y)\) が存在する条件は

• \(b = 3a \bmod 8\)
• \(1 \leq (3b-a)/8 \leq N\)
• \(1 \leq (3a-b)/8 \leq M\)

で，そのような \(b\) は (\(\bmod 8\) で) 連続する区間で表せます．またこの区間の左右は \(a\) について単調です．

よって，\(a\) を小さい方から試していき，各 mod 8 について使った最大の \(b\) を記録しておけば，貪欲に \(b\) を決めていくことができます．計算量は \(\mathrm{O}(N+M)\) です．