**Замечание: Время на тест в этой задаче 4s, в два раза больше чем по умолчанию.
Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**
У Фермера Джона \(N\) (\(2\le N\le 2\cdot 10^5\)) тракторов, где -ый трактор может использоваться
только в интервале \([l_i,r_i]\) включительно. Интервалы для тракторов имеют левые конечные точки
\(\ell_1<\ell_2<\dots<\ell_N\) и правые конечные точки \(r_1<r_2<\dots<r_N\).
Некоторые из тракторов специальные.
Два трактора \(i\) и \(j\) называются соседними если \([\ell_i,r_i]\) и
\([\ell_j,r_j]\) пересекаются. ФД может перебраться (выполнить трансфер) с одного
трактора на любой соседний трактор.
Путь между двумя тракторами \(a\) и \(b\) состоит трансферов таких, что
первый трактор в последовательности есть \(a\), последний трактор в последовательности
есть \(b\) и каждые два трактора в последовательности соседние. Гарантируется ,что
имеется путь из трактора \(1\) в трактор \(N\). Длина пути - количество трансферов
(или эквивалентно, количество тракторов минус один).
Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый указывает пару
тракторов \(a\) и \(b\) (\(1\le a<b\le N\)). Для каждого запроса выведите два
целых числа:
- Длину любого кратчайшего пути между тракторами \(a\) и \(b\).
- Количество специальных тракторов, таких, что существует как минимум
один кратчайший путь из трактора \(a\) в трактор \(b\), содержащий его.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(Q\).
Следующая строка содержит строку длины \(2N\), содержащую символы L и R,
представляющие левые и правые конечные точки в отсортированном порядке.
Гарантируется, что для каждого префикса этой строки количество символов L
превышает количество символов R.
Следующая строка содержит битовую строку длины \(N\), представляющую
для каждого трактора, является он специальным или нет.
Каждая из следующих \(Q\) строк содержит два целых числа \(a\) и \(b\),
описывающих запрос.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого запроса выведите два числа, разделённых пробелом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
|
1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2
|