편의상 1부터 N까지 번호가 매겨진 N (1 <= N <= 20)마리의 소들이 농부 존과 함께 한 게임을 하고 있다.

소들은 그들 스스로 한 라인에 정리되어있고, 그들의 라인 번호가 몇번인지 존에게 물어본다. 농부 존은 그들에게 라인 번호를 줄 수 있고 소들은 그들 스스로 그 라인 안으로 재배치해야 한다.

라인 넘버는 사전순으로 된 순열로 정해진다.

예를 들면, 농부 존은 5마리의 소가 있고, 사전순에 따라 증가하는 순열번호를 3을 물어보았다.

• 1st: 1 2 3 4 5
• 2nd: 1 2 3 5 4
• 3rd: 1 2 4 3 5

소들은, 대신, 스스로 "1 2 5 3 4"로 배치하고, 농부 존에게 그들의 라인번호를 물어본다.

• 4th : 1 2 4 5 3
• 5th : 1 2 5 3 4

농부 존과 소들은 그들이 게임하기 위해 당신의 도움을 원한다. 그들은 K (1 <= K <= 10,000) 개의 질문이 있다. 질문은 'P'와 'Q' 2가지로 나뉜다.

만약 질문이 'P'라면, 두번째 질문은 라인 넘버를 의미하는 정수 A_i(1 <= A_i <= N!)가 입력된다. 이것은 농부 존이 A_i번째 배치를 물어보는 것이다.

만약 질문이 'Q'라면, 두번째 줄에는 N개의 다른 정수 B_ij(1 <= B_ij <= N)가 입력된다. 이것은 소들의 번호를 기록한 것이다. 그들의 배치를 보고 농부 존이 몇번째 배치인지 맞추는 것이다.

입력

• 첫번째 줄에는 N과 K가 공백으로 나뉘어져 입력된다.
• 두번째 줄부터는 'P'나 'Q'를 입력받기 위한 한 줄, 그리고 그 이후 질문에 맞는 숫자들로 K개가 입력된다.

출력

입출력 예

입력 

5 2 
P 
3 
Q 
1 2 5 3 4 

출력 

1 2 4 3 5 
5 

입출력 보충

입력 (이해를 돕기 위해 하나 추가로 만들어보았습니다.) 

3 4 
P 
2 
P 
5 
Q 
1 3 2 
Q 
2 3 1 

출력 

1 3 2 
3 1 2 
2 
4 

입출력 보충 (입력 2) 

N이 3이 입력되면 사전순 배치는 다음과 같다. 

1 2 3 - 1 
1 3 2 - 2 
2 1 3 - 3 
2 3 1 - 4 
3 1 2 - 5 
3 2 1 - 6 

그러므로 질문에 따라 정답을 바로 알 수 있다. 

출처:usaco 2011 FEB silver
번역:pl0892029