思考题 featuring Hikari again!

Guess the string

Hikari and her master Ninetail are playing a game. Hikari thinks of a string S with lower-case letters, and Ninetail asks her to make q 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,R, get the substring from the L-th character to the R-th character inclusive. For example, aabbc with L=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 q operations, the final string is T. Find any S that satisfies the condition, or report impossible. (Note that if in operation 2 the indices are out of bound, such S is considered illegal).

You do not need to minimize the length of S.

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,q\leq 1000

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