In “Burrows-Wheeler Transform”, we introduced the Burrows-Wheeler transform of a string Text. In this problem, we give you the opportunity to reverse this transform.

Assignment

Implement the inverse_burrows_wheeler_transform method which takes a string containing a '$'.

The function should return the inverse Burrows-Wheeler transform of this string, which is equal to the original string we used to construct this.

Example

>>> inverse_burrows_wheeler_transform('TTCCTAACG$A')
'TACATCACGT$'
>>> inverse_burrows_wheeler_transform('ACTGGCT$TGCGGC')
'GCGTGCCTGGTCA$'