题目描述

WhiteCarrot被困在了一个会变化的迷宫中，请你帮帮他。

迷宫由多个方格组成，一共有 $n$ 行 $n$ 列。

迷宫会变化 $q$ 次。初始每个方格能够通向上下左右四个方向，每次变化会使某一个方格只能通往一个方向，同一个方格只会变化一次。

对于一个方格，如果他能通往迷宫外，就是可逃离的。

你需要在每次变化后告诉 WhiteCarrot 有多少个方格是可逃离的。

输入格式

第一行一个整数 $n$ 和一个整数 $q$ ,表示迷宫的大小和变化的次数。$(1 \leq n \leq 10^3,1\leq q \leq n^2)$

接下来 $q$ 行，每行两个整数 $x$,$y$ 和一个大写字母 $s$ 分别表示该次变化的方格坐标和变化后的方向。$(1\leq x,y \leq n,s\in \{U,D,L,R\})$

注：$U,D,L,R$分别表示上下左右四个方向。

输出格式

输出 $q$ 行，每行一个整数。第 $i$ 行表示第 $i$ 次变化后有多少方格是可逃离的。

输入输出样例 #1

输入 #1

2 4
1 1 R
1 2 D
2 1 U
2 2 L

输出 #1

4
4
4
0

提示/说明

本题输入量较大，请注意I/O效率

样例解释

样例1的迷宫在所有变化完成后形如

RD

UL

0个点可逃离，此前所有点均可逃离