SuffixTree(Text) can be constructed in linear time from SuffixArray(Text) by using the longest common prefix (LCP) array of Text, LCP(Text), which stores the length of the longest common prefix shared by consecutive lexicographically ordered suffixes of Text. For example, LCP("panamabananas$") is (0, 0, 1, 1, 3, 3, 1, 0, 0, 0, 2, 2, 0, 0).

Assignment

Given a string Text, SuffixArray(Text), and LCP(Text).

Return the strings labeling the edges of SuffixTree(Text). (You may return these strings in any order.)

Implement the suffix_array_to_tree method which takes a string, a suffix array (tuple) and a LCP (=longest common prefix) array (tuple).

The function should return the suffix tree of the string. The suffix tree should be formed in the class Node. This class should contain a __repr__(self) implementation, which returns a string in the following form: 'Node({label}, {children})'. Any other variables used in your implementation should not be included in this representation!

Example

>>> print(repr(suffix_array_to_tree('ACTT$', (4, 0, 1, 3, 2), (0, 0, 0, 0, 1)))
Node('', [Node('$', []), Node('ACTT$', []), Node('CTT$', []), Node('T', [Node('$', []), Node('T$', [])])])

>>> print(repr(suffix_array_to_tree('TCGAAG$', (6, 3, 4, 1, 5, 2, 0), (0, 0, 1, 0, 0, 1, 0)))
Node('', [Node('$', []), Node('A', [Node('AG$', []), Node('G$', [])]), Node('CGAAG$', []), Node('G', [Node('$', []), Node('AAG$', [])]), Node('TCGAAG$', [])])