Gọi \(S\) là tập các hoán vị của tập hợp \(\{1,2,\ldots,n\}\). Tập \(S\) được sắp xếp theo thứ tự từ điển.

• Cho một thứ tự từ điển, tìm hoán vị tương ứng
• Cho một hoán vị, tìm thứ tự từ điển tương ứng

Input

• Dòng đầu tiên ghi hai số nguyên \(N\) và \(K\) \((1\leq N \leq 20, 1 \leq K \leq 10000)\) là kích thước của hoán vị và số lượng các câu hỏi.
• Mỗi câu hỏi trong số K câu hỏi tiếp theo được ghi trên hai dòng:
  • Dòng đầu ghi ký tự Q hoặc P
  • Nếu dòng đầu ghi Q thì dòng thứ hai ghi một số nguyên dương nằm trong phạm vi từ \(1\) đến \(N!\), còn nếu dòng đầu ghi P thì dòng thứ hai ghi \(N\) số nguyên biểu thị một hoán vị của \((1,2,\ldots,N)\)

Output

• Nếu câu hỏi ứng với Q thì dòng tương ứng ghi một hoán vị của \((1,2,\ldots,N)\) có số thứ tự đã cho. Trường hợp ngược lại thì dòng tương ứng ghi số thứ tự

Example

5 2
P
3
Q
1 2 5 3 4

1 2 4 3 5
5