B3703.md

[语言月赛202301] 新年快乐

题目描述

扶苏收到的字符串是一个只含小写字母的字符串 $s$。

对于一个长度为 $x$ 的只含小写字母的字符串 $t$，我们定义 $t$ 的『上一个字符串』是：将所有的长度为 $x$ 且仅含小写字母的字符串按字典序排列后，恰好排在 $t$ 之前一个的字符串。

例如，字符串 $\texttt{bcd}$ 的『上一个字符串』是 $\texttt{bcc}$，而 $\texttt{aaa}$ 的『上一个字符串』不存在。

现在，扶苏有 $q$ 次询问，每次询问给出一个区间 $[l, r]$，查询：$s$ 的第 $l$ 个到第 $r$ 个字符组成的字符串的『上一个字符串』是否在 $s$ 中出现？

如果查询区间对应的字符串不存在『上一个字符串』，也算作『上一个字符串』没有在 $s$ 中出现。

输入格式

第一行是一个字符串，表示扶苏收到的字符串 $s$。
第二行有一个整数，表示询问的次数 $q$。
接下来 $q$ 行，每行两个整数，表示一次询问的 $l, r$。

输出格式

对于每次询问，输出两行，每行一个字符串。
对于每次询问的第一行输出，请输出对应字符串的『上一个字符串』。如果『上一个字符串』不存在，则输出 NULL。
对于每次询问的第二行输出，如果对应字符串的『上一个字符串』在 $s$ 中出现了，请输出 Happy New Year!，否则请输出 Happy Chinese New Year!。

样例 #1

样例输入 #1

bcdbccaacbzz
5
1 3
5 8
1 1
11 12
7 7

样例输出 #1

bcc
Happy New Year!
cbzz
Happy New Year!
a
Happy New Year!
zy
Happy Chinese New Year!
NULL
Happy Chinese New Year!

提示

数据规模与约定

以下以 $|s|$ 表示输入字符串 $s$ 的长度。

测试点编号	$\mid s \mid \leq$	$q=$	特殊约定
1	$1$	$1$	无
2	$20$	$7$	A,B
3	$20$	$8$	B
4	$20$	$9$	A
5	$400$	$198$	B
6	$400$	$199$	A
7	$400$	$199$	A
8	$400$	$200$	无
9	$400$	$200$	无
10	$400$	$200$	无

特殊约定 A：保证查询的字符串的『上一个字符串』在 $s$ 中出现。
特殊约定 B：保证查询的区间满足 $l = r$。

对全部的测试点，保证 $1 \leq |s| \leq 400$，$1 \leq q \leq 200$，$1 \leq l \leq r \leq |s|$，$s$ 中仅包含小写英文字母。

提示

你可以通过 $q$ 的末位数字来判定测试点所属的特殊约定信息。