트랙터 경로

Farmer John에게는 트랙터가 $N$대 ($2\le N\le 2\cdot 10^5$) 있다. $i$번째 트랙터는 닫힌 구간 $[\ell_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]$가 겹치면 두 트랙터는 인접한다고 한다. Farmer John은 한 트랙터에서 인접한 트랙터 중 아무 것으로나 옮겨 탈 수 있다. 트랙터 $a$에서 $b$까지의 경로는 $a$에서 시작해 $b$에서 끝나며, 연속한 두 트랙터가 모두 인접하는 환승의 나열이다. 트랙터 1에서 트랙터 $N$까지 가는 경로가 존재함이 보장된다. 경로의 길이는 환승 횟수이며, 경로에 포함된 트랙터 수에서 1을 뺀 값과 같다. $Q$개 ($1\le Q\le 2\cdot 10^5$)의 질의가 주어진다. 각 질의는 트랙터 한 쌍 $a$, $b$ ($1\le a<b\le N$)를 지정한다.

첫 줄에 $N$과 $Q$가 주어진다. 다음 줄에는 정렬된 순서대로 왼쪽 끝점과 오른쪽 끝점을 나타내는 길이 $2N$의 L과 R 문자열이 주어진다. 이 문자열의 모든 진접두사에서 L의 개수가 R의 개수보다 많다는 것이 보장된다. 그다음 줄에는 길이 $N$의 비트 문자열이 주어지며, 각 트랙터가 특별한지 여부를 나타낸다. 이어서 $Q$개의 줄에 각각 질의를 나타내는 두 정수 $a$, $b$가 주어진다.

각 질의마다 공백으로 구분한 두 정수를 출력한다. 첫 번째 값은 트랙터 $a$에서 $b$까지 가는 최단 경로 중 아무 것의 길이다. 두 번째 값은 트랙터 $a$에서 $b$까지의 최단 경로 중 하나 이상이 지나는 특별한 트랙터의 개수다.

트랙터 구간은 순서대로 $[1, 5]$, $[2, 10]$, $[3, 11]$, $[4, 12]$, $[6, 13]$, $[7, 14]$, $[8, 15]$, $[9, 16]$이다. 네 번째 질의에서 트랙터 1에서 5까지의 최단 경로는 세 개다. 1에서 2를 거쳐 5로 가는 경로, 1에서 3을 거쳐 5로 가는 경로, 1에서 4를 거쳐 5로 가는 경로이며, 모두 길이는 2다. 트랙터 1, 2, 3, 4, 5는 모두 이 세 최단 경로 중 하나에 속한다. 트랙터 1, 2, 4, 5가 특별하므로, 트랙터 1에서 5까지의 최단 경로 중 하나 이상에 속하는 특별한 트랙터는 4개다.