문제

AOJ 시스템에는 처리해야 할 업무들이 차례대로 들어온다. 각 업무에는 서로 다른 업무 번호와 우선순위가 있다. 우선순위는 정수로 표현되며, 값이 작을수록 더 높은 우선순위를 가진다.

각 업무는 들어온 뒤 처리되기 전까지 대기열에 남아 있다.

시스템은 업무 처리 요청이 들어올 때마다 다음 규칙에 따라 대기 중인 업무 하나를 처리한다.

• 기본 처리 규칙: 대기 중인 업무 중 우선순위 값이 가장 작은 업무를 처리한다.
• 동률 처리 규칙: 우선순위가 같은 업무가 여러 개라면, 그중 가장 먼저 들어온 업무를 처리한다.
• 강제 처리 규칙: 낮은 우선순위 업무의 기아 상태(Starvation)를 방지하기 위해, 우선순위 규칙으로 업무를 정확히 $K$개 처리한 뒤에는 다음 업무 처리 요청에서 우선순위와 관계없이 대기 중인 업무 중 가장 먼저 들어온 업무를 처리한다.

여기서 기아 상태란 우선순위가 낮다는 이유로 어떤 업무가 오랫동안 처리되지 못하고 계속 대기하는 상황을 뜻한다. 강제 처리로 처리된 업무는 우선순위 규칙으로 처리한 업무 개수에 포함되지 않으며, 강제 처리가 실제로 이루어진 뒤 우선순위 규칙으로 처리한 업무 개수는 $0$으로 초기화된다.

처리할 업무가 없는 상태에서 업무 처리 요청이 들어오면 -1을 출력한다. 이 경우 어떤 업무도 처리되지 않았으므로 우선순위 규칙으로 처리한 업무 개수는 변하지 않는다.

커맨드가 순서대로 주어질 때, 각 업무 처리 요청의 결과를 출력하시오.

입력

첫째 줄에 커맨드의 개수 $N$과 강제 처리 주기 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 1,000,000; 1 \le K \le 1,000)$

다음 $N$개의 줄 중 $j$번째 줄에는 $j$번째 커맨드가 주어진다. 각 커맨드는 다음 두 형식 중 하나이다.

• A i p: 업무 번호가 $i$이고 우선순위가 $p$인 업무가 대기열에 들어온다. A i p는 공백 하나로 구분된다. $(1 \le i \le N; 0 \le p \le 15)$
• B: 규칙에 따라 업무 하나를 처리한다. 이 줄에는 문자 B만 주어진다.

모든 A 커맨드에서 주어지는 업무 번호 $i$는 서로 다르다. 즉, 서로 다른 두 업무가 같은 업무 번호를 가질 수 없다.

입력에는 B 커맨드가 하나 이상 존재한다.

출력

각 B 커맨드마다 한 줄에 하나씩, 처리한 업무 번호를 출력한다. 처리할 업무가 없으면 -1을 출력한다.

예제 입력 1

8 2
A 1 5
A 2 3
A 3 1
B
A 4 1
B
B
B

예제 출력 1

3
4
1
2

예제 입력 2

12 2
A 1 5
A 2 1
A 3 0
B
B
A 4 0
B
B
A 5 2
A 6 1
B
B

예제 출력 2

3
2
1
4
6
5

힌트

처음 두 번의 B 커맨드는 우선순위 규칙으로 처리된다. 따라서 우선순위 값이 가장 작은 업무 3, 그다음으로 같은 우선순위 안에서 먼저 들어온 업무 4가 처리된다.

우선순위 규칙으로 업무를 $2$개 처리했으므로, 세 번째 B 커맨드에서는 강제 처리 규칙이 적용된다. 남은 업무 중 가장 먼저 들어온 업무는 1이므로 1이 처리된다.

마지막 B 커맨드에서는 다시 우선순위 규칙이 적용되어 남은 업무 2가 처리된다.

예제 2에서도 $K=2$이다. 처음 두 번의 B 커맨드는 우선순위 규칙으로 업무 3, 2를 처리한다. 이때 우선순위 규칙으로 처리한 업무 개수가 $2$가 되었으므로, 세 번째 B 커맨드는 강제 처리 규칙으로 업무 1을 처리한다. 업무 1은 우선순위 값이 더 크지만, 대기열에 가장 먼저 들어온 업무이기 때문이다.

강제 처리로 업무 1이 처리된 뒤 우선순위 규칙으로 처리한 업무 개수는 $0$으로 초기화된다. 따라서 네 번째 B 커맨드는 다시 우선순위 규칙으로 업무 4를 처리하고, 다섯 번째 B 커맨드도 우선순위 규칙으로 업무 6을 처리한다.

다시 우선순위 규칙으로 처리한 업무 개수가 $2$가 되었으므로, 여섯 번째 B 커맨드는 강제 처리 규칙으로 업무 5를 처리한다. 이처럼 강제 처리된 업무는 우선순위 규칙으로 처리한 업무 개수에 포함되지 않고, 강제 처리 뒤에는 그 개수가 다시 $0$이 된다.