Sort the Table

2000ms

65536K

Description:

You are given a rectangular table containing words. Each of its columns has its own name. You are also given the list of rules of sorting in form "FIELD_NAME SORT_ORDER", where SORT_ORDER is either ASC (nondescending order) or DESC (nonascending order). Rules in the list are separated by a single comma with a single space. You have to sort rows of the table primarily by the first rule, then, in case of a tie sort by the second rule. And so on. If two rows are equal in terms of every rule, then preserve their relative order. You can assume that each element of the table has type "string", so you have to use lexicographic comparison.

Input:

The first line contains column names. The second line contains the list of rules. The rest of the input data contains the table. All the words and column names are separated by single spaces. The number of rows and columns is between 1 and 100, inclusive. Names of columns and elements are strings containing only uppercase and lowercase Latin letters and digits, having the length between 1 and 10, inclusive.

Output:

Print the table after the sorting.

Sample Input:

NAME GROUP AGE
GROUP ASC, AGE DESC
Alex 412 19
Peter 422 19
Sergey 412 18
Andrey 311 18

Sample Output:

Andrey 311 18
Alex 412 19
Sergey 412 18
Peter 422 19

Informação

Provedor Codeforces

Código CF64I