经典结论：如果要比较两个无穷循环字符串 $A$ 和 $B$ 的大小，只需要比较 $AB$ 和 $BA$ 的大小就好了。

我们取 $s=a_{[l_i,r_i]}$，先扔掉 $t$ 不是 $s^{\infty}$ 前缀的情况，这个可以在后缀数组上二分。然后考虑：如果一个串是 $s^{\infty}$ 的前缀，那可能无法在一倍串长内判断。

先在原串里找一个最长的串 $t$，其是 $s^{\infty}$ 的前缀。它应该是 $t=s^ku$ 的结构，那么 $t^{\infty}$ 和 $s^{\infty}$ 的关系等价于 $u^{\infty}$ 和 $s^{\infty}$ 的关系。设 $s=uv$，根据我们的经典结论，两个无穷串的关系等价于 $su$ 和 $us$ 的关系，等价于 $vu$ 和 $uv$ 的关系。若 $v$ 不是 $s$ 的前缀，则其等价于 $v$ 和 $s$ 的大小关系，可以二维数点，两维分别是后缀的字典序和后缀的开始位置。

若 $v$ 是 $s$ 的前缀，那么继续取 $s=vw$，注意到 $|u|=|w|$，如果再出现 $w$ 是 $s$ 的前缀，那么 $w=u$ 不计数。

所以以上证明了：对于 $u$ 是 $s^{\infty}$ 的前缀，我们至多向后看一次循环就可以判断 $u^{\infty}$ 和 $s^{\infty}$ 的大小关系。然后就可以做出 $type=1$ 的特殊性质，即 $s^2$ 在 $a$ 中是存在的，拿出来上后缀数组就可以变成二维数点。

但是如果不存在，我们就只能找到一个字符串 $ss'$，其中 $s'$ 是 $s$ 的前缀。拿这个直接算是会算错的，所以考虑什么时候会算错。我们发现如果会算错那么至少要满足 $s=uv$，$v$ 是 $s$ 的前缀，即 $v$ 是 $s$ 的 border。

于是我们又有一个经典结论：一个字符串所有的 border 长度可以分成 $\log$ 个等差数列。我们可以分出若干个等差数列，每个在比较的时候都形如 $s=xy,xzy,xz^2y,\cdots$。这个东西是单调的，所以还是可以二分（单调的方向不一样要单独判）单个等差数列是单 $\log$ 的，这部分总复杂度就是 $q\log^2$ 的，总复杂度是 $O(n\log n+q\log^2 n)$。