2차원 컨베이어 벨트

Farmer John의 우유 공장은 컨베이어 벨트가 놓인 $N \times N$ 격자로 나타낼 수 있다 ($1 \le N \le 1000$). $(a,b)$ 칸은 위에서 $a$번째 행, 왼쪽에서 $b$번째 열에 있는 칸이다. 칸은 다음 다섯 종류 중 하나다. L은 왼쪽을 향한 벨트로, 그 위의 물건을 매 단위 시간마다 왼쪽으로 1칸 옮긴다. R은 오른쪽, U는 위쪽, D는 아래쪽으로 같은 방식으로 옮긴다. ?는 아직 벨트를 짓지 않은 칸이다. 벨트는 격자 밖으로도 물건을 옮길 수 있다. 칸 $c$에 놓인 물건이 격자 밖으로 영원히 나가지 못하고 격자 안에서 계속 움직인다면, $c$는 사용할 수 없는 칸이다.

처음에는 모든 칸이 ?다. 1일부터 $Q$일까지 매일 Farmer John은 벨트가 없는 칸을 하나 골라 벨트를 짓는다. $i$일에는 $(r_i,c_i)$ 칸에 종류 $t_i$의 벨트를 짓는다 ($1 \le r_i,c_i \le N$). 해당 칸에는 아직 벨트가 없음이 보장된다.

매일 하루가 끝난 뒤, 벨트가 없는 나머지 칸에 벨트를 최적으로 지었을 때 사용할 수 없는 칸의 최소 개수를 구하라.

첫 줄에 $N$과 $Q$가 주어진다. 이후 $Q$개의 줄에 각각 $r_i$, $c_i$, $t_i$가 순서대로 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$일이 끝난 뒤, 벨트가 없는 나머지 칸에 최적으로 벨트를 지었을 때 사용할 수 없는 칸의 최소 개수를 출력한다.