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 then 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.
Futhermore, a flag dir dictates the sorting direction.
ord(form highest priority to lowest priority).dir): If dir==1, sort the tickets in ascending order based on ord, otherwise, sort them in descending order based on ord. 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 digits (from smallest to largest).
It is guaranteed to contain all digits from '0' to '9' exactly once.
The following N lines each contain a string, representing the ticket numbers of the students.
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.