Comet OJ

C1767 [国庆欢乐赛]字符串

内存限制：256 MB 时间限制：1500 ms

题目描述

先来一些符号解释：

  • 对于任意字符串 $t$，我们把 $t$ 的长度记做 $|t|$。如： $t = $abc时， $|t| = 3$。
  • $t$ 是一个字符串，$t_{[a,b]}$ 表示 $t$ 由第 $a$ 个位置开始到第 $b$ 个位置的子串，且位置从 $0$ 开始编号。如：$t =$abcd时，$t_{[0,2]}$ =abc、$t_{[2,3]} = $cd。

给定一个字符串 $s$，有 $q$ 次询问，第 $i$ 次询问给定一个字符串 $t_i$，求最小的整数 $k$，满足以下两个条件：

1. $0 \le k \le |s| - |t_i|$ 。

2. $s_{[k,\ k\ +\ |t_i|\ -\ 1]}$ 的字典序大于 $t_i$。

对于每个询问请输出 $k$ 值，若不存在这样的 $k$，该询问请输出 $-1$。

输入格式

第一行有一个正整数 $q$ 代表询问的次数。

第二行有一个字符串 $s$。

接下来还有 $q$ 行，当中的第 $i$ 行包含一个字符串 $t_i$.

  • 所有字符串都有小写英文字母组成
  • $1 \le |s| \leq 2 \times 10^5$
  • $1 \le q \le 5000$
  • $\sum\limits_{i=1}^{q} |t_i| \leq 2 \times 10^5$

输出

输出 $q$ 行，每行一个整数，第 $i$ 行的整数代表第 $i$ 个询问的答案。

样例

样例输入 1

3
abcde
abc
cde
bde

样例输出 1

1
-1
2

提示