주유소

당신은 바쁜 주유소의 심야 근무자입니다. 모든 차량이 연료를 채우고 떠난 뒤에야 퇴근할 수 있습니다. 이 주유소에는 왼쪽에서 오른쪽으로 번호가 매겨진 $P$개의 주유기 기둥이 있고, 각 기둥에는 주유기 A와 주유기 B가 하나씩 있습니다. 주유기 하나는 연료 주입구가 오른쪽에 있는 차량이나 왼쪽에 있는 차량에 서비스할 수 있습니다. 한 주유기가 왼쪽 차량과 오른쪽 차량에 동시에 서비스할 수도 있습니다. 따라서 기둥마다 차량이 설 수 있는 차선이 두 개씩 있습니다.

차량은 엄격한 규칙에 따라 움직입니다. 차량은 주유구 방향에 맞는 차선 중 가장 왼쪽에 있는 열린 차선으로 갑니다. 열린 차선이 없으면 맞는 차선 중 대기열이 가장 짧은 곳에 섭니다. 가장 짧은 대기열이 여럿이면 그중 가장 왼쪽 차선에 섭니다. 일단 대기열에 들어간 차량은 다른 대기열로 옮길 수 없습니다. 차량이 떠나서 차선이 비면, 그 차선 대기열의 다음 차량이 주유기를 사용합니다.

주유기 A가 사용 가능하면 그 차선은 열려 있습니다. 주유기 B만 사용 가능하고 주유기 A가 사용 중이면 그 차선은 열려 있지 않습니다. 열린 차선에 간 차량은 두 주유기가 모두 비어 있으면 주유기 B를 쓰고, 그렇지 않으면 주유기 A를 씁니다. 새 차량이 막 주유를 마치고 떠난 다른 차량과 같은 시각에 도착하면, 새 차량은 대기열의 다른 차량들이 열린 주유기로 모두 옮겨 갈 때까지 기다린 뒤에 어디에 설지 정합니다. 주유기 A에서 떠나는 차량은 앞쪽 주유기 B가 사용 중이어도 즉시 떠날 수 있습니다.

차량 $i$는 시각 $t_i$에 도착하고, 주유하고 떠나는 데 $f_i$분이 조금 안 되게 걸리며, 주유구는 $s_i$ 쪽에 있습니다.

첫 줄에 두 정수 $P$와 $N$이 주어집니다. $1\leq P\leq 10$은 주유기 기둥의 수이고, $1\leq N\leq 1000$은 도착할 차량의 총 수입니다. 다음 $N$개의 줄에는 각각 정수 $t_i$, $f_i$와 문자 $s_i$가 공백으로 구분되어 주어집니다. $s_i$는 R 또는 L입니다. 여기서 $1\leq t_i\leq 10^5$, $1\leq f_i\leq 100$입니다. 모든 $1\leq i<N$에 대해 $t_i<t_{i+1}$입니다.

$N$개의 줄을 출력합니다. $i$번째 줄에는 입력에서 $i$번째로 주어진 차량이 주유소를 떠나는 시각을 출력합니다.