该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

要过春节了，小红收到了她的新年礼物：一个崭新的字符串。

题目描述

小红收到的字符串是一个只含小写字母的字符串 $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!。

样例

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

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

提示

数据规模与约定

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

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