P9019 [USACO23JAN] Tractor Paths P

**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 $[l_i,r_i]$. The tractor intervals have left endpoints $l_1

The first line contains $N$ and $Q$. The next line contains a string of length $2N$ consisting of Ls and Rs, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of Ls exceeds the number of Rs. 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.

### Explanation for Sample 1 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 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. ### Scoring - Inputs $2-3$: $N,Q \le 5000$ - Inputs $4-7$: There are at most $10$ special tractors. - Inputs $8-16$: No additional constraints.