Farmer John has $N (2≤N≤2⋅10^5)$ tractors, where the ith tractor can only be used within the inclusive interval $[l_i,r_i]$. The tractor intervals have left endpoints $l_1 \lt l_2\lt ⋯\lt l_N$ and right endpoints $r_1 \lt r_2 \lt ⋯\lt r_N$. Some of the tractors are special.

Two tractors $i$ and $j$ are said to be adjacent if $[l_i,r_i]$ and $[l_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≤Q≤2⋅10^5)$ queries, each specifying a pair of tractors $a$ and $b (1≤a\lt b≤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.

The first line contains $N$ and $Q$.
The next line contains a string of length $2N$ consisting of $L$s and $R$s, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of $L$s exceeds the number of $R$s.

The next line contains a bit string of length $N$, representing for each tractor whether it is special or not.

The next $Q$ lines each contain two integers $a$ and $b$, specifying a query.

For each query, the two quantities separated by spaces.

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 $4$th query, there are three shortest paths between the 1st and 5th 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.