소 줄 세우기

$N$마리의 소($1 \le N \le 20$)가 $1$번부터 $N$번까지 번호를 달고 한 줄로 선다. 소들이 설 수 있는 모든 배열은 $1$부터 $N$까지의 순열이며, 모든 순열을 사전순(오름차순)으로 나열했을 때의 위치를 그 배열의 줄 번호라고 한다. 줄 번호는 $1$부터 시작한다.

요청은 두 종류이다.

• P: 줄 번호 $A$($1 \le A \le N!$)가 주어지면, 그 줄 번호에 해당하는 소들의 배열을 출력한다.
• Q: 소들의 배열(즉 $1$부터 $N$까지의 순열)이 주어지면, 그 배열의 줄 번호를 출력한다.

예를 들어 $N = 5$일 때, 사전순으로 나열한 순열은 다음과 같이 시작한다.

1번째: 1 2 3 4 5
2번째: 1 2 3 5 4
3번째: 1 2 4 3 5
4번째: 1 2 4 5 3
5번째: 1 2 5 3 4

따라서 줄 번호 $3$에 해당하는 배열은 1 2 4 3 5이고, 배열 1 2 5 3 4의 줄 번호는 $5$이다.

총 $K$개($1 \le K \le 10000$)의 요청이 주어지며, 각 요청에 답해야 한다.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

이어지는 $2K$개의 줄에 $K$개의 요청이 한 요청당 두 줄씩 주어진다. 각 요청은 다음과 같다.

• 첫 줄에는 문자 P 또는 Q 하나가 주어진다.
• P이면 다음 줄에 정수 $A$($1 \le A \le N!$) 하나가 주어진다. 이 줄 번호에 해당하는 배열을 구해야 한다.
• Q이면 다음 줄에 서로 다른 $N$개의 정수가 주어진다. 이 배열의 줄 번호를 구해야 한다.

각 요청에 대한 답을 입력에 주어진 순서대로 한 줄씩 출력한다.

• P 요청에는 해당하는 배열을 $N$개의 정수로 공백으로 구분하여 출력한다.
• Q 요청에는 그 배열의 줄 번호를 정수 하나로 출력한다.