Tractor Paths

Farmer John has $N$ ($2\le N\le 2\cdot 10^5$) tractors. Tractor $i$ can only be used within the closed interval $[\ell_i, r_i]$. The left endpoints satisfy $\ell_1<\ell_2<\dots<\ell_N$, and the right endpoints satisfy $r_1<r_2<\dots<r_N$. Some of the tractors are special. Two tractors $i$ and $j$ are adjacent if $[\ell_i, r_i]$ and $[\ell_j, r_j]$ intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between tractors $a$ and $b$ is a sequence of transfers that starts at $a$, ends at $b$, and has every pair of consecutive tractors adjacent. It is guaranteed that a path exists between tractor 1 and tractor $N$. The length of a path is the number of transfers, which equals the number of tractors in it minus one. You are given $Q$ ($1\le Q\le 2\cdot 10^5$) queries. Each query gives a pair of tractors $a$ and $b$ ($1\le a<b\le N$).

The first line contains $N$ and $Q$. The next line contains a string of length $2N$ made of L and R, giving the left and right endpoints in sorted order. It is guaranteed that every proper prefix of this string has more Ls than Rs. The next line contains a bit string of length $N$, where each bit says whether the corresponding tractor is special. The next $Q$ lines each contain two integers $a$ and $b$, specifying a query.

For each query, print two integers separated by a space. The first is the length of any shortest path from tractor $a$ to tractor $b$. The second is the number of special tractors that lie on at least one shortest path from tractor $a$ to tractor $b$.

The $8$ tractor intervals, in order, are $[1, 5]$, $[2, 10]$, $[3, 11]$, $[4, 12]$, $[6, 13]$, $[7, 14]$, $[8, 15]$, $[9, 16]$. For the 4th query, there are three shortest paths between tractor 1 and tractor 5: 1 to 2 to 5, 1 to 3 to 5, and 1 to 4 to 5. All of them have length 2. Tractors 1, 2, 3, 4, and 5 each lie on one of these shortest paths. Since tractors 1, 2, 4, and 5 are special, there are 4 special tractors that lie on at least one shortest path from tractor 1 to tractor 5.