小张的好朋友小松要过生日了，小张打算为他挑选一件礼物。在市场上他发现有一个珠子手镯的商店很不错。在这家商店会出售特殊的珠子并穿成一个手镯，在货架上珠子排成一排，每一个珠子上有一个小写英文字母。店家有一个特殊的规定，必须在一排珠子中按顺序从左到右挑选。小张心中已经有一个想要送给小松的单词，请你告诉他应该如何挑选珠子使得手镯上珠子的字母组成小张想要的单词。

Input

第一行，一个字符串，表示货架上的一排珠子，仅包含小写英文字母，长度在200000以内。

第二行，一个字符串，表示小张想要的单词，仅包含小写英文字母，长度在10000以内。

Output

输出一行整数，表示小张按照从左到右需要挑选的珠子在货架上的位置。

Notes

从左到右按顺序选出的珠子上的字母为'p'，'p'，'y'，'h'，'a'。串成环形的手镯后可以组成"happy"。

数据保证有解，若有多种选取方法，输出其中字典序最小的一个，比如1 2 3 4比1 3 4 5的字典序小。

提交后查看结果页面错误信息一栏，前4行的编译错误大家不用理会，第5行是关于你的结果的信息。

测试用例：

input

????????pxrtpsapyjhuvab

????????happy

output

????????1?5?9?11?14

心路历程

1 自己尝试TLE

其实这道题乍一看很简单，不就是遍历吗。

然而TLE路上等你，说多了都是泪。

2 论坛无果

论坛的信息太过零散，大多是一种个人总结，带有装逼性质的那种，顺便混点分。这种不会讲太细，看不懂是很正常的。比如下面这个，现在回头看，他说的都是非常正确的，而且是很关键的，但是当时怎么就看不懂呢？关键出在基础知识上。

3 柳暗花明

无意间看到有人说子序列自动机，我依稀想起舍友之前和我说过这个东西。

当时舍友和我说的时候我上csdn看了看，感觉太难了，就没再看过，结果最后碰的头破血流，回头发现当时看起来最难的东西，可以说几乎是做出这道题AC的唯一途径，否则就是TLE。

于是就开始漫长的子序列自动机的学习。

子序列自动机怎么学？

1 为什么要子序列自动机？

逐字符遍历耗时太久，我们需要跳跃。

跳到哪里呢？比如我要找happy，我现在已经找到了h，那我能不能直接跳到后面第一个a呢？可以，只要我们储存了那个a的编号就可以，子序列自动机应运而生。

2 学习资料

https://blog.csdn.net/qq_43109145/article/details/89429411?spm=1001.2014.3001.5506

这篇文章因为有图解，所以比较清晰易懂，但是有一个重大缺陷，那就是这个程序会跑错（破防），也就是说，她的思想是对的，但是有细节错误，所以这篇文章就供大家建立对子序列自动机的基本认识：横坐标代表什么？纵坐标代表什么？如何根据给出的带筛选字符串构造一个子序列自动机二维数组？如何用取出来的一种环（比如appyh）去跳跃遍历这个子序列自动机？

剩下的文章，大家也可以搜着看，核心都是一样的，就是建立自动机，然后遍历。

3 补充思路

其实要看懂自动机，最好还是有个思路在前。如果没有一个宏观思路，那么去看代码很容易只见树木不见森林，这里提供一下宏观思路：

首先要遍历所有可能的组合，类似：happy，appyh，直到yhapp

我们可以使用happyhappy字符串，从h到y每次顺次读取5个字符就可以实现，如果不想扩展字符串也可以用%运算来实现模仿环形。

对于每一种可能的5个字符，要在自动机中遍历，自动机的作用简单说就是加快遍历的速度，从一个一个遍历，到跳跃遍历。

好，如果能成功遍历到我们目标的5个字符，那么这个组合就是有解的。

之后就要判断是否是最优解了，这里要用一个ans数组储存最终的答案，用temp数组去做缓冲。这里涉及到一个字典序的的定义，字典序大家百度一下，其实就是类似于strcmp函数，只不过我们比较的内容超出了char范围，所以手写一个对int生效的“intcmp”函数，如果temp的字典序小于ans，那么就是更优解，那么就把temp写入ans，以此类推。

最后输出ans即可，因为不断优化，最后剩下的就是最优解了。

好的，到这里，就把大致的思路介绍完了，那么之后无论是学习子序列自动机或者看我的代码，都可以比较容易的看懂。