AC#1~#7,#10,#13

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
int ans;
bool ok[1005][1005];//ok
bool vis[1005][1005];
char tp[1005][1005];
/*bool dfs(int x,int y){
	if(x<1||y<1||x>n||y>n)return 1;
	if(vis[x][y])return ok[x][y];	
	vis[x][y]=1;
	if(tp[x][y]==0){
		if(dfs(x+1,y)||dfs(x,y+1)||dfs(x,y-1)||dfs(x-1,y)){
			ok[x][y]=1;
		}
	}else if(tp[x][y]=='U'){
		if(dfs(x-1,y)){
			ok[x][y]=1;
		}
	}else if(tp[x][y]=='D'){
		if(dfs(x+1,y)){
			ok[x][y]=1;
			return 1;
		}
	}else if(tp[x][y]=='L'){
		if(dfs(x,y-1)){
			ok[x][y]=1;
		}
	}else if(tp[x][y]=='R'){
		if(dfs(x,y+1)){
			ok[x][y]=1;
		}
	}
	return ok[x][y];
}*/
void dfs2(int x,int y){
	if(x<1||y<1||x>n||y>n)return;
	if(ok[x][y])return;	
	ans++;
	ok[x][y]=1;
	if(tp[x-1][y]=='D'||tp[x-1][y]==0){
		dfs2(x-1,y);
	}
	if(tp[x+1][y]=='U'||tp[x+1][y]==0){
		dfs2(x+1,y);
	}
	if(tp[x][y-1]=='R'||tp[x][y-1]==0){
		dfs2(x,y-1);
	}
	if(tp[x][y+1]=='L'||tp[x][y+1]==0){
		dfs2(x,y+1);
	}
}
bool ck(int x,int y){
	if(x<1||x>n||y<1||y>n)return 1;
	return ok[x][y];
}
int x[200005],y[200005];
int an[200005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("P11454_8.in","r",stdin);
//	freopen("P11454.out","w",stdout);
	memset(tp,0,sizeof tp);
	memset(vis,0,sizeof vis);
	memset(ok,0,sizeof ok);
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>x[i]>>y[i];
		cin>>tp[x[i]][y[i]];
	}
	for(int i=1;i<=n;i++){
		if(tp[1][i]=='U')dfs2(1,i);
		if(tp[n][i]=='D')dfs2(n,i);
		if(tp[i][n]=='R')dfs2(i,n);
		if(tp[i][1]=='L')dfs2(i,1);
	}
	an[q]=n*n-ans;
	for(int i=q;i>1;i--){
		if(!ok[x[i]][y[i]]){	
			if(ck(x[i]-1,y[i])||ck(x[i]+1,y[i])||ck(x[i],y[i]-1)||ck(x[i],y[i]+1)){
				dfs2(x[i],y[i]);
			}
		}
		tp[x[i]][y[i]]=0;
		an[i-1]=n*n-ans;
	}
	for(int i=1;i<=q;i++){
		cout<<an[i]<<'\n';
	}
	return 0;
}