Cow Line Game

The problem involves ordering cows in a line based on their lexicographic permutation order. Given a number of cows \(N\) (with \(1 \leq N \leq 20\)) and \(K\) queries, each query is one of two types:

• P: Given a line number \(A\) (where \(1 \leq A \leq N!\)), output the corresponding permutation of cows in lexicographic order. In other words, find the \(A^{th}\) permutation of the sequence \(1, 2, \ldots, N\).
• Q: Given a permutation of the cows (a rearrangement of \(1, 2, \ldots, N\)), compute its lexicographic rank (the position in the ordered list of all permutations). The ranking is 1-indexed.

For example, for \(N=5\) and the queries:
Query 1: P 3 (the 3rd permutation is computed as follows)
The lexicographic order begins with: 1 2 3 4 5, 1 2 3 5 4, 1 2 4 3 5, ... so the answer is 1 2 4 3 5.
Query 2: Q 1 2 5 3 4 yields the rank 5 because 1 2 5 3 4 is the 5th permutation.

Your task is to process \(K\) queries. When the query starts with 'P', you need to generate the permutation corresponding to the given line number. When the query starts with 'Q', you need to compute the lexicographic rank of the given permutation.

Note: All factorial related formulas should be represented in \(\LaTeX\). For example, the factorial of \(n\) is given by \(n!\) and the range of \(N\) is \(1 \leq N \leq 20\).

inputFormat

The first line contains two integers \(N\) and \(K\), where \(N\) is the number of cows and \(K\) is the number of queries.

Then \(K\) queries follow. Each query is in one of the following formats:

• P A where \(A\) is an integer representing the line number (\(1 \leq A \leq N!\)).
• Q B1 B2 \ldots BN where \(B_i\) are distinct integers representing a permutation of the cows.

outputFormat

For each query, output the result in a new line. For a query of type 'P', output the permutation (space-separated). For a query of type 'Q', output the lexicographic rank of the given permutation.

sample

5 2
P 3
Q 1 2 5 3 4

1 2 4 3 5
5