[语言月赛202301] 新年快乐

扶苏收到的字符串是一个只含小写字母的字符串 $s$。 对于一个长度为 $x$ 的只含小写字母的字符串 $t$，我们定义 $t$ 的『上一个字符串』是：将所有的长度为 $x$ 且仅含小写字母的字符串按字典序排列后，恰好排在 $t$ 之前一个的字符串。 例如，字符串 $\texttt{bcd}$ 的『上一个字符串』是 $\texttt{bcc}$，而 $\texttt{aaa}$ 的『上一个字符串』不存在。 现在，扶苏有 $q$ 次询问，每次询问给出一个区间 $[l, r]$，查询：$s$ 的第 $l$ 个到第 $r$ 个字符组成的字符串的『上一个字符串』是否在 $s$ 中出现？ 如果查询区间对应的字符串不存在『上一个字符串』，也算作『上一个字符串』没有在 $s$ 中出现。 ## Input 第一行是一个字符串，表示扶苏收到的字符串 $s$。 第二行有一个整数，表示询问的次数 $q$。 接下来 $q$ 行，每行两个整数，表示一次询问的 $l, r$。 ## Output 对于每次询问，输出两行，每行一个字符串。 对于每次询问的第一行输出，请输出对应字符串的『上一个字符串』。如果『上一个字符串』不存在，则输出 `NULL`。 对于每次询问的第二行输出，如果对应字符串的『上一个字符串』在 $s$ 中出现了，请输出 `Happy New Year!`，否则请输出 `Happy Chinese New Year!`。 [samples] ## Background 要过春节了，扶苏收到了她的新年礼物：一个崭新的字符串。 ## Note ### 数据规模与约定 以下以 $|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$ 的末位数字来判定测试点所属的特殊约定信息。