新年快乐

来源：洛谷 B3703（[语言月赛202301] 新年快乐）

题目描述

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

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

例如，字符串 bcd 的『上一个字符串』是 bcc，而 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$ 的长度。

特殊约定 A：保证查询的字符串的『上一个字符串』在 $s$ 中出现。

特殊约定 B：保证查询的区间满足 $l = r$。

对全部的测试点，保证 $1 \le |s| \le 400$，$1 \le q \le 200$，$1 \le l \le r \le |s|$。