낭만적인 영화 나들이

브라이언은 애나테브카와 함께 영화관에 간다. 이 영화관에는 $1000$개의 좌석으로 이루어진 행이 $10^9$개 있으며, 처음에는 모든 좌석이 비어 있다. 행은 스크린에서 가장 가까운 행부터 $1 \dots 10^9$로 번호가 매겨져 있고, 각 행의 좌석은 왼쪽부터 오른쪽으로 $1 \dots 1000$번으로 번호가 매겨져 있다. $r$행의 $c$번째 좌석을 $(r, c)$로 나타낸다. $1 \dots L$행($1 \le L \le 1000$)의 좌석은 스크린에 가까운 좌석이고, 그보다 뒤쪽 행의 좌석은 먼 좌석이다.

영화가 시작되기 전 $T$분($1 \le T \le 500000$) 동안 여러 사건이 일어난다. $i$번째 분에는 문자 $E_i$와 두 정수 $R_i, C_i$로 표현되는 다음 세 가지 중 정확히 하나가 일어난다.

• $E_i =$ E: 어떤 사람이 들어와 비어 있는 좌석 $(R_i, C_i)$에 앉는다.
• $E_i =$ L: 차 있는 좌석 $(R_i, C_i)$에 앉아 있던 사람이 떠난다.
• $E_i =$ S: 애나테브카가 좌석 $(R_i, C_i)$와 $(R_i, C_i + 1)$을 제안한다.

사건에 등장하는 모든 좌석은 유효한 좌석이며, 애나테브카가 제안하는 좌석은 항상 가까운 좌석이다(즉 S 사건에서는 $R_i \le L$).

좌석 $(r, c)$의 시야는, $(1, c)$까지의 맨해튼 거리가 $(r, c)$의 그것보다 크지 않은 모든 좌석의 집합이다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 맨해튼 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다. $(1, c)$에서 $(r, c)$까지의 거리는 $r - 1$이므로, 좌석 $(x, y)$가 $(r, c)$의 시야에 들어오는 것은 $(x - 1) + |y - c| \le r - 1$, 즉 $x + |y - c| \le r$일 때이며, 자기 자신은 제외한다.

좌석 $(r, c)$의 불편도는 그 시야 안에 있는(자기 자신은 세지 않는) 차 있는 좌석의 수이다.

제안(S)이 있을 때마다 브라이언은 그것을 평가한다. 제안된 두 좌석 중 하나라도 이미 차 있으면 그 제안은 무효이다. 그렇지 않으면 제안의 질은 제안된 두 좌석의 불편도의 합이다.

모든 사건이 끝난 뒤 브라이언이 최종 선택을 한다. 그는 먼 빈 좌석을 선호하며, 두 좌석이 서로 인접할 필요는 없다. 서로 다른 두 개의 먼 빈 좌석의 불편도 합의 최솟값을 구하여라. 선택한 한 좌석이 다른 좌석의 시야에 들어오더라도 그것은 불편도에 더해지지 않는다. 불편도는 오직 영화관에 앉아 있는 다른 사람들에 의해서만 정해진다.

첫째 줄에 두 정수 $L$과 $T$가 주어진다($1 \le L \le 1000$, $1 \le T \le 500000$).

다음 $T$개의 줄에는 각각 문자 $E_i$($E_i \in \{$ E, L, S $\}$)와 두 정수 $R_i$, $C_i$가 주어진다($1 \le R_i \le 10^9$, $1 \le C_i \le 1000$), $i = 1 \dots T$. S 사건에서는 두 번째 좌석 $(R_i, C_i + 1)$도 유효해야 하므로 $C_i \le 999$이다.

각 제안(S 사건)에 대해 입력에 주어진 순서대로, 제안이 무효이면(두 좌석 중 하나 이상이 차 있으면) No를, 그렇지 않으면 제안된 두 좌석의 불편도 합을 출력한다.

마지막으로 한 줄에, 서로 다른 두 개의 먼 빈 좌석 쌍의 불편도 합의 최솟값을 출력한다.