#B3703. [语言月赛202301] 新年快乐

    ID: 102 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2023O2优化字符串(入门)语言月赛

[语言月赛202301] 新年快乐

题目背景

要过春节了,扶苏收到了她的新年礼物:一个崭新的字符串。

题目描述

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

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

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

现在,扶苏有 qq 次询问,每次询问给出一个区间 [l,r][l, r],查询:ss 的第 ll 个到第 rr 个字符组成的字符串的『上一个字符串』是否在 ss 中出现?

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

输入格式

第一行是一个字符串,表示扶苏收到的字符串 ss
第二行有一个整数,表示询问的次数 qq
接下来 qq 行,每行两个整数,表示一次询问的 l,rl, r

输出格式

对于每次询问,输出两行,每行一个字符串。
对于每次询问的第一行输出,请输出对应字符串的『上一个字符串』。如果『上一个字符串』不存在,则输出 NULL
对于每次询问的第二行输出,如果对应字符串的『上一个字符串』在 ss 中出现了,请输出 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| 表示输入字符串 ss 的长度。

测试点编号 s\mid s \mid \leq q=q= 特殊约定
1 11
2 2020 77 A,B
3 88 B
4 99 A
5 400400 198198 B
6 199199 A
7
8 200200
9
10

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

对全部的测试点,保证 1s4001 \leq |s| \leq 4001q2001 \leq q \leq 2001lrs1 \leq l \leq r \leq |s|ss 中仅包含小写英文字母。

提示

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