Tractor Paths and Special Counts

Farmer John has \(N\) tractors (\(2 \le N \le 2\cdot10^5\)); the \(i\)-th tractor is available during the inclusive interval \([l_i, r_i]\). It is guaranteed that \(l_1 < l_2 < \cdots < l_N\) and \(r_1 < r_2 < \cdots < r_N\). In addition, some tractors are special.

Two tractors \(i\) and \(j\) (with \(i\neq j\)) are adjacent if their intervals intersect, i.e. if \[ \max(l_i, l_j) \le \min(r_i, r_j). \] Farmer John is allowed to transfer between adjacent tractors. A path from tractor \(a\) to tractor \(b\) is a sequence of transfers starting at tractor \(a\) and ending at tractor \(b\) such that every two consecutive tractors in the sequence are adjacent. The length of a path is defined as the number of transfers (or one less than the number of tractors on the path).

It is guaranteed that there is at least one path between tractor 1 and tractor \(N\). You are given \(Q\) queries (\(1 \le Q \le 2\cdot10^5\)). Each query consists of a pair of integers \(a\) and \(b\) (with \(1 \le a < b \le N\)). For each query, output two integers:

• The length of any shortest path from tractor \(a\) to tractor \(b\).
• The number of special tractors for which there exists at least one shortest path from tractor \(a\) to tractor \(b\) that contains that tractor.

Note: The time limit for this problem is 4 seconds and the memory limit is 512MB.

inputFormat

The input is given as follows:

N Q
s1 s2 ... sN
l1 r1
l2 r2
...
lN rN
a1 b1
a2 b2
...
aQ bQ

Where:

• \(N\) is the number of tractors.
• \(Q\) is the number of queries.
• Each \(s_i\) is an integer (0 or 1) indicating whether tractor \(i\) is special (1 means special).
• For each tractor \(i\), \(l_i\) and \(r_i\) denote the available interval. It is guaranteed that \(l_1 < l_2 < \cdots < l_N\) and \(r_1 < r_2 < \cdots < r_N\).
• Each of the following \(Q\) lines contains two integers \(a\) and \(b\) (with \(1 \le a < b \le N\)), representing a query.

outputFormat

For each query, print two space‐separated integers in one line:

• The length (number of transfers) of a shortest path from tractor \(a\) to tractor \(b\).
• The number of special tractors that appear in at least one shortest path from \(a\) to \(b\).

sample

5 3
1 0 1 0 1
1 5
2 3
4 6
5 7
6 8
1 5
2 4
3 5

2 3
2 1
1 2