冠军野牛不仅仅是一头野牛。他也是“Bizons”队的最爱。
在一次比赛中,“Bizons”遇到了以下问题:“给你两个不同的单词(英文字母串),s 和 t。你需要将单词 s 转换为单词 t”。对于这些人来说,这项任务看起来很简单,因为他们非常了解后缀数据结构。 Bizon Senior 喜欢后缀自动机。通过将其应用于字符串一次,他可以从该字符串中删除任何单个字符。 Bizon Middle 非常了解后缀数组。通过将其应用于字符串一次,他可以交换该字符串的任意两个字符。这些人对后缀树一无所知,但它可以帮助他们做更多的事情。
冠军 Bizon 想知道“Bizons”能否解决这个问题。也许,该解决方案不需要这两种数据结构。看看这些人是否可以解决问题,如果可以,他们是如何解决的?他们可以仅使用后缀自动机或仅使用后缀数组来解决这个问题,还是需要这两种结构?注意,任何结构可以无限次地使用,结构可以以任何顺序使用。
输入
第一行包含一个非空单词 s。第二行包含一个非空单词 t。单词 s 和 t 是不同的。每个单词仅由小写英文字母组成。每个单词最多包含 100 个字母。
输出
在单行中打印问题的答案。如果即使同时使用后缀数组和后缀自动机,单词 s 也无法转换为单词 t,则打印“need tree”(不带引号)。如果您只需要后缀自动机来解决问题,请打印“自动机”(不带引号)。如果只需要后缀数组来解决问题,请打印“array”(不带引号)。如果您需要两种数据结构来解决问题,请打印“both”(不带引号)。
可以保证的是,如果仅使用后缀数组可以解决问题,那么仅使用后缀自动机就不可能解决该问题。对于后缀自动机也是如此。
示例
输入 #1
automaton tomat
输出 #1
automaton
输入 #2
array arary
输出 #2
array
输入 #3
both hot
输出 #3
both
输入#4
need tree
输出#4
need tree
注意
在第三个示例中,您可以这样做:首先使用后缀自动机删除第一个字符,将“both”转换为“oth”,然后使用后缀数组对字符串进行两次交换并获得“hot”。