Orange Boy Can You Solve It Out? Ep. 61

思考题 featuring Hikari again!

Guess the string

Hikari and her master Ninetail are playing a game. Hikari thinks of a string SS with lower-case letters, and Ninetail asks her to make qq modifications one by one. Each modification can only be one of the following two forms:

  • append itself to the back of the string. For example aabbc will turn into aabbcaabbc after this operation.

  • Given L,RL,R, get the substring from the L-th character to the R-th character inclusive. For example, aabbc with L=2,R=4L=2,R=4 will get abb. It is made sure that the range will not be out of bound.

It is known that after all these qq operations, the final string is TT. Find any SS that satisfies the condition, or report impossible. (Note that if in operation 2 the indices are out of bound, such SS is considered illegal).

You do not need to minimize the length of SS.

Example

Input:

Queries=[{1},{2,L=1,R=3},{1},{2,L=1,R=4}]
T="abaa"

Output:

S="ab"

Explanation:

ab->abab->aba->abaaba->abaa

Input:

Queries=[{2,L=1,R=3},{1},{2,L=1,R=7},{1}]
T="abcdefgabcdefg"

Output:

Impossible

Limitations

For 80%, L,R,q1000L,R,q\leq 1000

For 100%, L,R,q105L,R,q\leq 10^5

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/1566
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录

Example

关闭
目 录