Cabi is a sad I2P TA. He was planning to hold a lottery for the students, wanting to pick a few lucky ones in a special order to give them some rewards. This special order was carefully written on a piece of paper.
However, yesterday he used some of his paper to solve a terrifying math problem, and gave the remaining pieces to students during the lab because some of them were suffering and needed paper to trace their code.
Having no paper left, Cabi only has a chaotic list of student ticket numbers and faintly remembers the sorting rule. Please help Cabi reconstruct the sorted list and find the lucky students.
Cabi remembers that the tickets are not sorted in the standard alphabetical or numerical order.
Instead, they follow a custom character priority defined by a string ord.
Furthermore, a flag dir dictates the sorting direction.
Custom Lexicographical Order: You must compare the strings based on the character priority given in ord (from highest priority to lowest priority).
Direction (dir): If dir == 1, sort the tickets in ascending order based on ord, otherwise, sort the tickets in descending order based on ord.
Prefix Rule: If two tickets have different lengths but the shorter one is entirely a prefix of the longer one, the shorter one is always considered "smaller".
The first line contains three integers: N Q dir
N: the total number of students' tickets.Q: the number of lucky students Cabi wants to query.dir: the sorting direction (1 for ascending, 0 for descending).The second line contains a string ord, representing the custom order of all possible characters (from smallest to largest).
It is guaranteed that ord contains each of the following characters exactly once:
'0' to '9''A' to 'Z''a' to 'z'The following N lines each contain a string, representing the ticket numbers of the students.
Each ticket consists only of digits (0-9) and English letters (A-Z, a-z).
The following Q lines each contain an integer k (0-indexed). For each query, you need to output the k-th ticket in the sorted list.
For each query k, output the ticket string at index k in the sorted list, followed by a newline.