농부 존의 우유 공장은 N \times N (1 ≤ N ≤ 1,000) 크기의 격자로 표현될 수 있으며, 각 격자는 컨베이어 벨트를 포함하고 있습니다. 위치 (a, b)는 위에서부터 a번째 행, 왼쪽에서부터 b번째 열에 해당하는 셀을 나타냅니다. 격자의 셀은 5가지 유형 중 하나로 나타낼 수 있습니다:

L: 왼쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 왼쪽으로 한 칸씩 이동합니다.
R: 오른쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 오른쪽으로 한 칸씩 이동합니다.
U: 위쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 위쪽으로 한 칸씩 이동합니다.
D: 아래쪽으로 이동하는 컨베이어 벨트로, 물건이 매 단위 시간마다 아래쪽으로 한 칸씩 이동합니다.
?: 해당 셀에 아직 컨베이어 벨트가 설치되지 않은 상태를 나타냅니다.

컨베이어 벨트는 격자 바깥으로도 물건을 이동시킬 수 있습니다. 특정 셀 c는 만약 해당 셀에서 시작한 물건이 격자 바깥으로 나가지 못하고 영원히 격자 안에서 움직이는 경우 "사용 불가"로 간주됩니다.

초기에 농부 존은 공장을 건설하지 않았으므로 모든 셀은 ?로 시작합니다. 앞으로 Q일 동안 (1 ≤ Q ≤ 2 ⋅ 10^5), 농부 존은 컨베이어 벨트가 설치되지 않은 셀을 선택하여 컨베이어 벨트를 설치할 예정입니다.

특히, i번째 날에는 농부 존이 위치 (r_i, c_i)에 유형 t_i(t_i ∈ {L, R, U, D})의 컨베이어 벨트를 설치합니다. 위치 (r_i, c_i)에는 이미 컨베이어 벨트가 없다는 것이 보장됩니다.

각 날이 끝날 때마다, 농부 존이 남은 모든 ? 셀에 대해 최적으로 컨베이어 벨트를 설치하여 사용 불가 셀의 최소 수를 계산하는 것을 도와주세요.

#8181 upload 9 done 5 how_to_reg 5 call_split Subtask

2D 컨베이어 벨트 timer 2s memory 1024MB

#8181
Subtask

2D 컨베이어 벨트 2s 1024MB