题目背景

尛焱轟在玩字符串。。。

题目描述

对于一个长度为的字符串,的后缀表示的长度为的后缀.
给定一个字符串,有若干次询问,每次给定,询问的后缀和的后缀的最长公共前缀的长度的最大值.
由于这道题目过于简单,要求强制在线,令表示上一次询问的答案(初始值为),则每一次实际的询问为.

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

输入格式

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

输出格式

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

样例输入

7

aabcaab

3

2 4 7

1 6 5

0 3 4

样例输出

2

1

3

样例解释

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

数据范围

对于全部数据,,解密之后的询问满足.