**Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.**

Farmer John has $N$ ($2\le N\le 2\cdot 10^5$) tractors, where the $i$th tractor can only be used within the inclusive interval $[\ell_i,r_i]$. The tractor intervals have left endpoints $\ell_1<\ell_2<\dots<\ell_N$ and right endpoints $r_1<r_2<\dots<r_N$. Some of the tractors are special.

Two tractors $i$ and $j$ are said to be 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 two tractors $a$ and $b$ consists of a sequence of transfers such that the first tractor in the sequence is $a$, the last tractor in the sequence is $b$, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor $1$ and tractor $N$. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given $Q$ ($1\le Q\le 2\cdot 10^5$) queries, each specifying a pair of tractors $a$ and $b$ ($1\le a<b\le N$). For each query, output two integers:

• The length of any shortest path between tractor $a$ to tractor $b$.
• The number of special tractors such that there exists at least one shortest path from tractor $a$ to tractor $b$ containing it.

SAMPLE INPUT:

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

SAMPLE OUTPUT:

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

For the $4$th query, there are three shortest paths between the $1$st and $5$th tractor: $1$ to $2$ to $5$, $1$ to $3$ to $5$, and $1$ to $4$ to $5$. These shortest paths all have length $2$.

Additionally, every tractor $1,2,3,4,5$ is part of one of the three shortest paths mentioned earlier, and since $1,2,4,5$ are special, there are $4$ special tractors such that there exists at least one shortest path from tractor $1$ to $5$ containing it.

Problem credits: Benjamin Qi