\(Y=W\) の場合、答えは \(X=Z\) なら \(0\)、そうでないならば \(1\) です。

\(Y>W\) の場合、\(X\) と \(Z\)、\(Y\) と \(W\) を swap すればよいため、\(Y<W\) と仮定してよいです。

まず、重要な事実として移動中に通った階の番号は単調増加または単調減少となります。

よって、この問題は連絡通路を使う回数の最小化と同値です。

そして、同じビルにあって共通部分を持つエレベーターをマージします。例えば、ビル \(1\) に \(3\) 階から \(7\) 階を結ぶエレベーターと \(5\) 階から \(10\) 階を結ぶエレベーターがあったとします。この場合、両者を削除して変わりに \(3\) 階から \(10\) 階を結ぶエレベーターを追加します。

次に、ビル \(X\)の \(Y\) 階を通るエレベーターがあればそのエレベーターの最上階まで移動します。同様に、ビル \(Z\) の \(W\) 階を通るエレベーターがあればそのエレベーターの最下階まで移動します。この時点で \(Y \le W\) となった場合の扱いに注意してください。(特に \(X=Z\) の場合)

ここで、「\(\mathrm{DP}[i][j] =\) 今あるエレベーターの一番上まで登った段階で \(i\) 階にいる時、ここから \(j\) 回連絡通路を使えるとすると何階まで上がることができるか」を考えます。

このままでは時間計算量が間に合いませんが、座圧をした上で「\(\mathrm{DP}[i][j] =\) 今あるエレベーターの一番上まで登った段階で \(i\) 階にいる時、ここから \(2^j\) 回連絡通路を使えるとすると何階まで上がることができるか」としてダブリングをすると毎クエリ \(\mathrm{O}( \log M)\) で処理することができます。

よってこの問題を解くことができました。計算量はダブリングの前計算を合わせ、 \(\mathrm{O}((M+Q)\log M)\) です。