B. Общий префикс суффиксов двух строк

Даны две строки и запросы: какой длины наибольший общий префикс у суффикса $s$, начинающегося в позиции $i$, и суффикса $t$, начинающегося в позиции $j$.

Тот же двоичный поиск по хешам, что и в классе, но хеши теперь от разных строк.

Здесь важно, чтобы обе строки хешировались одним и тем же основанием и модулем: иначе хеши несравнимы, и сравнение всегда будет давать «не равны». Это частая ошибка, и проявляется она как «ответ всегда ноль» - легко заметить, если проверить на двух одинаковых строках.

Ограничения по времени такие же: $O((\lvert s \rvert + \lvert t \rvert) + q \log)$.

В первой строке - строка $s$, во второй - строка $t$. Обе непусты, длины не превосходят $10^5$, состоят из строчных латинских букв.

В третьей строке - число запросов $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $i$, $j$ ($1 \le i \le \lvert s \rvert$, $1 \le j \le \lvert t \rvert$).

Для каждого запроса выведите длину наибольшего общего префикса.