Задача . 2D Conveyor Belt

Молочная фабрика Фермера Джона может быть описана решёткой из \(N\) * \(N\) ячеек (\(1 \le N \le 1000\)), которые содержат конвейерные ленты. Позиция (\(a,b\)) описывает ячейку, которая находится в строке \(a\) сверху и столбце \(b\) слева. �меется \(5\) типов ячеек.

1. "L" — перемещает все элементы на 1 ячейку влево каждую единицу времени.
2. "R" — перемещает все элементы на 1 ячейку вправо каждую единицу времени.
3. "U" — перемещает все элементы на 1 ячейку вверх каждую единицу времени.
4. "D" — перемещает все элементы на 1 ячейку вниз каждую единицу времени.
5. "?" — ФД не построил ещё конвейерный двигатель в этой ячейке.

Заметим, что конвейеры могу перемещать элементы за решётку. Ячейка \(c\) является неиспользуемой если предмет, размещенный в ячейке \(c\) никогда не покинет решётку, он будет всегда двигаться внутри решётки.

�значально, ФД ещё не начал строить фабрику, поэтому все ячейки содержат "?". Для следующих \(Q\) (\(1 \le Q \le 2 \cdot 10^5\)) дней начиная со дня \(1\) и заканчивая днём \(Q\), , ФД выбирает свободную ячейку и строит в ней конвейер.

А именно, в течение \(i\)-го дня ФД строит конвейер типа \(t_i\) (\(t_i \in {\text{{L,R,U,D}}}\)) в позиции (\(r_i,c_i\)) (\(1 \le r_i,c_i \le N\)). Гарантируется, что конвейера нет в позиции (\(r_i,c_i\)).

После каждого дня помогите ФД найти минимальное количество неиспользованных ячеек, которое он может достичь, оптимально строя конвейеры во всех оставшихся свободных ячейках.

ПР�МЕР ВВОДА:

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

ПР�МЕР ВЫВОДА:

0
0
0
2
3

RL?
U??
?DL

Один оптимальный способ построить конвейер в оставшихся ячейках представлен ниже.

RLR
URR
LDL

ПР�МЕР ВВОДА:

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

ПР�МЕР ВЫВОДА:

0
2
2
4
4
6
6
9

RLD
D?U
URL

ПР�МЕР ВВОДА:

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

ПР�МЕР ВЫВОДА:

0
0
0
0
0
0
0
0
11
11
11
11
13

Автор: Alex Liang

0
0
0
2
3