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.

INPUT FORMAT (input arrives from the terminal / stdin):

OUTPUT FORMAT (print output to the terminal / stdout):

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

SCORING:

• Inputs 2-3: $N,Q\le 5000$
• Inputs 4-7: There are at most 10 special tractors.
• Inputs 8-16: No additional constraints.

Problem credits: Benjamin Qi