나룻배

강 양쪽에는 두 정박장이 있으며, 각각 left와 right로 구분한다. 나룻배는 처음에 left 정박장에 있다. 나룻배는 한 번에 최대 M명을 태울 수 있고, 어느 방향으로 건너든 이동에는 t만큼의 시간이 걸린다.

나룻배가 한 정박장에 도착하면, 먼저 그 정박장이 목적지인 승객을 모두 내려준다. 그런 다음 그 정박장에서 기다리는 승객을 최대 M명까지 태운다. 승객이 타는 데 걸리는 시간은 0이며, 더 오래 기다린 승객이 먼저 탄다. 승객을 태운 뒤에는 반대쪽 정박장으로 이동한다.

도착한 정박장에 기다리는 승객이 없다면, 나룻배는 그곳에서 다음 승객을 기다린다. 기다리는 동안 반대쪽 정박장에 승객이 먼저 도착하면, 나룻배는 그쪽 정박장으로 이동한다.

각 승객이 어느 정박장에 언제 도착하는지가 주어질 때, 입력으로 주어진 순서대로 각 승객이 목적지에 도착하는 시간을 구하시오.

첫째 줄에 세 정수 M, t, N이 주어진다.

다음 N개의 줄에는 각 승객이 정박장에 도착하는 시간과 도착한 정박장의 위치가 주어진다. 정박장의 위치는 left 또는 right이다. 승객의 도착 시간은 100000 이하의 음이 아닌 정수이다.

N개의 줄에 입력으로 주어진 순서대로 각 승객이 목적지에 도착하는 시간을 출력한다.

• 1 ≤ M ≤ 10,000
• 1 ≤ t ≤ 10,000
• 1 ≤ N ≤ 10,000