Passport Journey

On a planet there are \(N\) countries numbered from \(1\) to \(N\). Each country issues its own passport. When a traveler holds the passport from country \(i\) \( (1 \le i \le N)\), he is allowed to enter all the countries in the interval \(\left[L_i, R_i\right]\). It is guaranteed that \(L_i \le i \le R_i\), so the country issuing the passport is always within its valid range.

A friend who loves traveling wishes to visit all \(N\) countries. Initially, he has no passport. He plans to travel by repeating the following two actions:

• Obtain a passport issued by the country where he is currently located.
• Move to any country that he can enter using one of the passports he currently holds.

Your task is to determine, for each possible starting country \(X\), whether it is possible for him to eventually visit all \(N\) countries. If it is possible, compute the minimum number of passports needed (including the one obtained in the starting country). If not, output -1.

Note: When the friend is at a country, he may choose any passport (from any country he can reach) to further extend his reach. The friend may only obtain a passport if the corresponding country is within his current reachable range.

The problem can be modeled as finding a sequence of passports (each associated with an interval) beginning with the one from the starting country, such that the union of their intervals eventually covers the entire range \([1, N]\). For a given starting country \(X\), let the initial reachable interval be \(\left[L_X, R_X\right]\). Then, in each move, the friend may go to any country within the current interval and acquire its passport. This will update the current interval to the union \(\Bigl[\min(\text{current }L, L_i), \max(\text{current }R, R_i)\Bigr]\). The goal is to cover \(1\) and \(N\) with the minimum number of acquisitions.

inputFormat

The input begins with an integer \(N\) \( (1 \le N)\) representing the number of countries. The following \(N\) lines each contain two integers \(L_i\) and \(R_i\) \( (1 \le L_i \le i \le R_i \le N)\) separated by a space, representing the valid interval for the passport issued by country \(i\).

Next, an integer \(Q\) is given, representing the number of queries. The next line contains \(Q\) integers \(X_1, X_2, \dots, X_Q\) (each \(1 \le X_j \le N\)), where each \(X_j\) is a possible starting country of the traveler.

outputFormat

For each query, output a single line containing one integer: the minimum number of passports required to visit all \(N\) countries, or -1 if it is impossible.

sample

5
1 3
1 2
2 5
3 5
4 5
3
1 3 5

2
2
4