题目背景

尛焱轟在玩字符串。。。

题目描述

对于一个长度为n的字符串s,s的后缀i(1\leq{i}\leq{n})表示s的长度为n-i+1的后缀.
给定一个字符串s,有若干次询问,每次给定x,l,r,询问s的后缀xs的后缀i(l\leq{i}\leq{r})的最长公共前缀的长度的最大值.
由于这道题目过于简单,要求强制在线,令lastans表示上一次询问的答案(初始值为0),则每一次实际的询问为(x\oplus{lastans},l\oplus{lastans},r\oplus{lastans}).

注意这里的\oplus表示异或运算.

输入格式

第一行一个整数n,表示给定字符串的长度.
第二行一个字符串s,表示给定的字符串.
第三行一个整数q,表示询问的次数.
接下来q行,每行三个整数x,l,r,表示一次询问.

输出格式

输出q行,每行一个整数,表示询问的答案.

样例输入

7

aabcaab

3

2 4 7

1 6 5

0 3 4

样例输出

2

1

3

样例解释

解密之后的询问为(2,4,7),(3,4,7),(1,2,5).

数据范围

对于全部数据,\small 1\leq{n,q}\leq{10^5},解密之后的询问满足\small 1\leq{x}\leq{n},1\leq{l\leq{r}}\leq{n}.