\(A = B\) のときは答えは明らかに Yes です。以降 \(A \neq B\) とします。

操作は異なる整数 \(i,j\) を選んで \(A_i,A_j\) をそれぞれ \(\max(A_i+A_j-M,0),\min(A_i+A_j,M)\) に置き換える操作と言い換えることが出来ます。

\(A \neq B\) であるため \(1\) 回以上の操作が必要になりますが、操作を \(1\) 回でも行うと \(A_i,A_j\) のどちらかが \(0,M\) のどちらかになるので、\(B\) が \(0,M\) をどちらも含まなければ答えは No です。

逆に、\(B\) が \(0,M\) のどちらかを含むならば、\(A_i = 0,M\) なる \(i\) と他の \(j\) を選び操作することで \(A_i,A_j\) を swap する操作となるため、\(A,B\) を多重集合として一致させることが出来ればよいです。

\(A,B\) を多重集合として一致させることが出来る必要十分条件は、\(\sum A = \sum B\) かつ「\(A\) の要素を \(N\) 個の集合 \(S_1,S_2,\dots,S_N\) (空でもよい) に分割して、各 \(i\) について \(S_i\) の要素の総和と \(B_i\) を \(\bmod\ M\) で等しくできる」ことです。より厳密には、以下の通りです。

• 長さ \(N\) の正整数列 \(x=(x_1,x_2,\dots,x_N)\) であって、以下の条件を満たすものが存在する。
  • 全ての \(i\) に対して、\(1 \le x_i \le N\)
  • 全ての \(k\) に対して、\(C_k = \sum_{x_i = k} A_i \bmod M\) と置く。\(B,C\) は \(\bmod\ M\) で(つまり \(B\) の \(M\) を \(0\) に置き換えると)等しい

必要性を証明します。\(\sum A = \sum B\) が必要であることは自明なので、\(x\) についての条件について証明します。始めは各 \(i\) に対して \(x_i = i\) としておきます。そして、操作で \(i,j\) を選ぶごとに、\(x\) に含まれる全ての \(x_j\) を \(x_i\) に置き換えます。すると、条件を満たす \(x\) を得ることが出来ます。

十分性を証明します。各 \(k\) に対して、\(x_i = k\) を満たすバケツ \(i\) の水を全てあるバケツにまとめます。そのような \(i\) が存在するバケツについてはまとめたバケツに欲しい水量が入っています。存在しない \(i\) については \(B_i = 0,M\) のいずれかですが、\(\sum A = \sum B\) であるため \(0,M\) の個数についても問題ありません。

以降、\(\sum A = \sum B\) を仮定し、\(X_i\) を \(A\) に含まれる \(i\) の個数、\(Y_i\) を \(B\) に含まれる \(i\) の個数とします。まず、\(0,M\) は同一視していいため \(X_0,Y_0\) を \(X_0+X_M,Y_0+Y_M\) に置き換えたうえで \(X_M,Y_M\) を削除してしまってよいです。ここで、\(\sum A = \sum B\) により \(A\) の全ての要素を \(S\) に振り分ける必要は実はありません。余った要素は総和が \(\bmod\ M\) で \(0\) だからです。よって、\(\bmod\ M\) で「\(X_i\) 個の \(i(0 \le i < M)\)」を用いて「\(Y_i\) 個の \(i(0 \le i < M)\)」を余ってもいい条件下で作れるか、という問題になります。

まず、\(Y_0\) は空集合で満たせるため \(Y_0 = 0\) としてしまってよいです。そして、\(X_i,Y_i \ge 1\) のときは \(i\) を \(1\) 個使い \(i\) を作ってしまってもよいです。もし全ての \(i\) を \(\lbrace i \rbrace\) 以外で作るとした場合、以下のどちらかを実行すれば \(\lbrace i \rbrace\) で \(i\) を作ることのある解を構築できます。

• \(i\) が余っているときは、いずれかの \(i\) を \(\lbrace i \rbrace\) で作ったことにする。
• \(i\) が余っていないときは、\(i\) 以外を作るために \(i\) が使われている。その使われている \(i\) と、\(i\) を作るために使った \(\lbrace i \rbrace\) 以外の集合を swap する。

これを繰り返すことで、\(\min(X_i,Y_i) = 0\) である状況に出来ます。ここで、\(Y_i > 0\) である場合に \(i\) が不足していると言うこととします。どの \(i\) が不足しているかで場合分けを行います。

これ以降、\(i\) を作るためには \(S_1,S_2,\dots,S_k\) の選択肢があります。という文が何度も現れますが、これは以下の条件を満たす多重集合 \(S\) を列挙しています。

• \(\sum S \equiv i \pmod M\)
• \(S\) に同じ要素が \(M\) 個以上含まれることはない。
• \(T \subsetneq S,|T| \neq 0,\sum T \equiv 0 \pmod M\) を全て満たす部分集合 \(T\) は存在しない。

\(M = 1\)

可能です。

\(M = 2\)

• どれも不足していないとき

可能です。

• $1$ が不足しているとき

不可能です。

\(M = 3\)

• どれも不足していないとき

可能です。

• $1$ のみ不足しているとき

$\lbrace 2,2 \rbrace$ で $1$ を作るしかないため、$2Y_1 \le X_2$ が可能である条件です。

• $2$ のみ不足しているとき

全ての要素を $2$ 倍することで $1$ のみ不足しているケースに帰着できます。条件は $2Y_2 \le X_1$ となります。

• $1,2$ がどちらも不足しているとき

不可能です。

\(M=4\)

• どれも不足していないとき

可能です。

• $1$ のみ不足しているとき

$\lbrace 2,3 \rbrace,\lbrace 3,3,3 \rbrace$ の $2$ 個の選択肢があります。まず $1$ の個数分だけ $3$ が必要で、$1$ 個ずつ $3$ を使うと $\lbrace 2 \rbrace,\lbrace 3,3 \rbrace$ のどちらかをさらに加えればいいため、条件は $Y_1 \le X_3$ かつ $Y_1 \le \frac{X_3-Y_1}{2} + Y_2$ です。

• $2$ のみ不足しているとき

$\lbrace 1,1 \rbrace,\lbrace 3,3 \rbrace$ の $2$ 個の選択肢があります。どちらも独立しているため、条件は $Y_2 \le \left \lfloor \frac{X_1}{2} \right \rfloor + \left \lfloor \frac{X_3}{2} \right \rfloor$ です。

• $3$ のみ不足しているとき

全ての要素を $3$ 倍することで $1$ のみ不足しているケースに帰着できます。条件は $Y_3 \le X_1$ かつ $Y_3 \le \frac{X_1-Y_3}{2} + Y_2$ です。

• $1,2$ が不足しているとき

$1$ を $\lbrace 3,3,3 \rbrace$ で、$2$ を $\lbrace 3,3 \rbrace$ で作るしかありません。よって、条件は $3Y_1 + 2Y_2 \le X_3$ となります。

• $1,3$ が不足しているとき

$2$ をいくつ組み合わせても $\bmod\ 4$ で $1,3$ にならないため不可能です。

• $2,3$ が不足しているとき

全ての要素を $3$ 倍することで $1,2$ が不足しているケースに帰着できます。条件は $3Y_3 + 2Y_2 \le X_1$ となります。

• $1,2,3$ が全て不足しているとき

不可能です。

よって全てのケースを解くことが出来ました。計算量は \(M\) を定数として \(\mathrm{O}(Q)\) です。