各参加者 \(i\) に対し、長さ \(K\) の数列 \(X_i\) を、

\(X_{i,j}=\begin{cases} 0 & S_{i,j}=T_{j}のとき\\ 1 & S_{i,j}\neq T_{j}のとき\\ \end{cases}\)

により定めます。

\(N=M\) のときは、\(X_i=(1,1,1,\dots)\) であることが、答えが No であるための必要十分条件です。

\(N\neq M\) のとき、クエリは次のように読み替えられます。

• \(X_{i,j}\) を反転させる。その後、 \(X_1,\dots,X_N\) の中に辞書順で \(X_i\) と同じかより小さいものが \(M\) 個以下であるかを判定する

（これが元の問題と同値であることは、与えられた選抜方法により \(N\) 人全員に順位をつけることを考えると明らかです）

このクエリは \(X\) を trie で管理することで、各クエリで1回ずつ行う削除・追加・計数をそれぞれ \(O(K)\) で処理することができ、問題を \(O((N+Q)K)\) で解くことができました。

また別解として、 プライオリティーキューや ordered multiset を用いて上位 \(M\) 個を管理するデータ構造を用いることでもこの問題を \(O((N+Q\log N)K)\) で解くことができます。（参考 ABC281E）