Circular RNA

题号：NC210141
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

环状RNA(circular RNA,circRNA)是一类经反向剪接后、由3'末端和5'末端共价结合形成的环状非编码RNA(non-coding RNA,nc RNA)分子,广泛存在于多种生物细胞中,具有结构稳定、序列保守及细胞或组织特异性表达等特征。

在circRNA上常常储存有很多块信息，但是在一种特殊的circRNA上，有一块信息被称作终止信息。为了方便研究，我们假设这个circRNA上共有 $n$ 块信息，每一块信息都可以用一个小写英文字母表示。同时按顺时针顺序从某个点开始将每一块分别标号1...n，使得终止信息块标号为 $n$ 。

这种circRNA的特殊结构导致了其特殊的读取方式。当我们要以第i块信息作为起点开始读取时，按照顺时针顺序从i开始依次读取每一块信息，并将代表该块信息的字符按顺序记录，直到终止块上的信息第二次被记录。最终所记录字符所组成的字符串成为本次读取的读取结果。显然，我们从1...n块信息作为起点，会得到 $n$ 个长度互不相同的读取结果。

为了研究这种circRNA的相关信息，对于一个信息已知的circRNA，你需要给出所有读取结果中字典序第k大的结果的起始读取位置。

输入描述:

第一行包含数据组数().
接下来有组数据，每组数据中:
第一行包含一个字符串()，代表circRNA上含有的信息。保证终止信息位于最后一位。
第二行包含一个正整数()，代表有组询问。
接下来行，每行有一个正整数()

输出描述:

对于每一组测试数据，输出包括行，分别为每一组询问的答案。

示例1

输入

复制

1
caba
4
1
2
3
4

输出

复制

说明

样例中的四个结果排序后分别为：abacaba,acaba,bacaba,cabacaba
第一次询问：=0,=2
第二次询问：=4,=3
第三次询问：=3,=1
第四次询问：=2,=3

备注:

本题的每一组询问包含一个数,对于该询问，你需要回答读取结果中第大的结果的起始读取位置，其中=( XOR )mod+1,其中为信息总块数，XOR代表按位异或。代表上一次询问的答案。对于第一次询问，。