If \(B=D\), then the answer is \(0\) if \(A=C\) or \(1\) otherwise.

If \(B>D\), we may swap \(A\) and \(C\), and \(B\) and \(D\), so we may assume that \(B<D\).

First, an important fact is that the floors to pass through is either monotonically increasing or decreasing.

Therefore, this problem boils down to minimizing the number of uses of skybridges.

Let us merge elevators in the same building common floors. For example, suppose that Skyscraper \(1\) has an elevator running from Floor \(3\) to Floor \(7\), and another from Floor \(5\) to Floor \(10\). In such case, we may remove both of them and add an elevator running from Floor \(3\) to Floor \(10\) instead.

Next, if there is an elevator passing through Floor \(B\) of Skyscraper \(A\), then move to the highest floor of the elevator. Similarly, if there is an elevator passing through Floor \(D\) of Skyscraper \(C\), then move to the lowest floor of the elevator. Beware of the cases where \(B \le D\) is already satisfied at this point (especially when \(A=C\)).

Here, consider \(\mathrm{DP}[i][j] =\) the highest floor you can reach using \(j\) elevators, starting from floor \(i\) that is the highest possible floor of the elevator available in that floor of the current building.

While this costs too much time complexity, we may do coordinate compression and use doubling technique as “\(\mathrm{DP}[i][j] =\) the highest floor you can reach using \(2^j\) elevators, starting from floor \(i\) that is the highest possible floor of the elevator available in that floor of the current building,” so that each query can be processed in an \(\mathrm{O}( \log M)\) time.

Therefore, the problem has been solved. The time complexity is \(\mathrm{O}((M+Q)\log M)\), including the precalculation of the doubling.