컴퓨터 과학 광인 브라이언은 여자친구인 아나테브카와의 데이트 계획을 세우고 있습니다. 장소는 바로 영화관입니다. (다만 IMAX는 너무 비싼 관계로 일반 영화관을 선택했습니다)
이 영화관은 10^9개의 행과 1000개의 열의 좌석으로 이루어져있습니다. 처음 영화관은 텅 비어있습니다. 각 행은 스크린에 가장 가까운 행부터 1부터 10^9까지 번호가 주어져있고, 각 열은 왼쪽부터 오른쪽으로 1부터 1000번까지 번호가 주어져있습니다. r번째 행 c번째 좌석은 (r,c)로 표시할 수 있습니다. 1...L번 행 좌석들은 스크린에 '가까운' 좌석이고 나머지는 '먼' 좌석입니다.
영화가 시작되기 T (1 ≤ T ≤ 500000) 분 전부터 여러가지 일이 일어납니다. i분에 사람이 한 명 들어와 빈 자리 (Ri, Ci)에 앉거나, (Ri, Ci)에 앉아있는 사람이 영화관 밖으로 나가거나, 아나테브카가 브라이언과 (Ri, Ci), (Ri, Ci+1) 자리에 앉자고 제안합니다. i분에 일어나는 사건은 문자 Ei로 표현될 수 있는데 Ei = 'E'는 사람이 들어오는 사건, Ei = 'L'은 사람이 나가는 사건, Ei = 'S'는 아나테브카가 브라이언에게 제안을 하는 사건입니다. 각 사건에서 언급될 좌석들은 전부 유효한 좌석들입니다. 또한 아나테브카는 '가까운' 좌석이 좋다며 그녀가 제안하는 모든 좌석은 언제나 '가까운' 좌석입니다.
아나테브카가 좌석을 제안할 때마다 브라이언은 이 좌석이 얼마나 좋은 좌석인지를 분석해야합니다. 둘 중 한 좌석이라도 이미 다른 사람이 차지하고 있다면 간단히 'No' 라고 답변해주면 됩니다. 아니면 이 두 좌석이 얼마나 불편한지를 계산해서 알려줘야합니다. 좌석 (r,c)의 불편한 정도는 좌석 (r,c)의 시야에 얼마나 많은 사람이 있는지로 결정됩니다. 좌석 (r,c)의 시야는 (r,c)부터 스크린 방향으로 대각선으로 퍼져 나가 포함되는 모든 좌석들이 포함됩니다. 아래 그림에서 S는 아나테브카가 제안한 좌석이고 F는 S의 시야입니다.
모든 사건이 종료되고 영화가 곧 시작하려 하는 관계로 최종 결정을 내려야 할 때입니다. 브라이언은 '먼' 좌석이 넓은 시야를 제공하므로 '가까운' 좌석보다 훨씬 좋다고 생각합니다. 그리고 영화관에 가는 목적은 영화를 즐겁게 보기 위해서이므로 두 사람이 바로 옆 자리에 앉아야만 할 필요는 없습니다. 브라이언은 아무 '먼' 두 좌석의 불편한 정도가 가장 적은 두 좌석을 고르려고 합니다. 여기서 고른 한 좌석이 다른 한 좌석의 시야에 가려져도 불편한 정도가 올라가진 않습니다.
입력 3 7 E 1 2 E 2 5 S 3 4 E 2 3 L 2 5 S 1 3 S 2 2 출력 3 0 No 0
출처:CEMC (CCC 2013 Stage 2) 번역:ladown21