```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

const INF = 2000000000

type SegTree struct {
	minVal []int
}

func NewSegTree(n int) *SegTree {
	st := &SegTree{
		minVal: make([]int, 4*n+1),
	}
	for i := range st.minVal {
		st.minVal[i] = INF
	}
	return st
}

func (st *SegTree) Update(node, start, end, idx, val int) {
	if start == end {
		st.minVal[node] = val
		return
	}
	mid := (start + end) / 2
	if idx <= mid {
		st.Update(2*node, start, mid, idx, val)
	} else {
		st.Update(2*node+1, mid+1, end, idx, val)
	}
	if st.minVal[2*node] < st.minVal[2*node+1] {
		st.minVal[node] = st.minVal[2*node]
	} else {
		st.minVal[node] = st.minVal[2*node+1]
	}
}

// Query finds the rightmost index in [1, qR] such that value <= threshold
func (st *SegTree) Query(node, start, end, qR, threshold int) int {
	if start > qR || st.minVal[node] > threshold {
		return -1
	}
	if start == end {
		return start
	}
	mid := (start + end) / 2
	res := -1
	if mid+1 <= qR {
		res = st.Query(2*node+1, mid+1, end, qR, threshold)
	}
	if res != -1 {
		return res
	}
	return st.Query(2*node, start, mid, qR, threshold)
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n_dummy int64
	var q int
	fmt.Fscan(in, &n_dummy, &q)

	type Query struct {
		x, y int
		dir  byte
	}
	qs := make([]Query, q)
	xs := make([]int, 0, q)
	ys := make([]int, 0, q)

	for i := 0; i < q; i++ {
		var x, y int
		var s string
		fmt.Fscan(in, &x, &y, &s)
		qs[i] = Query{x, y, s[0]}
		xs = append(xs, x)
		ys = append(ys, y)
	}

	sort.Ints(xs)
	sort.Ints(ys)

	uX := make([]int, 0, q)
	if len(xs) > 0 {
		uX = append(uX, xs[0])
		for i := 1; i < len(xs); i++ {
			if xs[i] != xs[i-1] {
				uX = append(uX, xs[i])
			}
		}
	}
	uY := make([]int, 0, q)
	if len(ys) > 0 {
		uY = append(uY, ys[0])
		for i := 1; i < len(ys); i++ {
			if ys[i] != ys[i-1] {
				uY = append(uY, ys[i])
			}
		}
	}

	xMap := make(map[int]int, len(uX))
	for i, v := range uX {
		xMap[v] = i + 1
	}
	yMap := make(map[int]int, len(uY))
	for i, v := range uY {
		yMap[v] = i + 1
	}

	numX, numY := len(uX), len(uY)
	treeU := NewSegTree(numX) // Indexed by X-rank, stores Y-coordinate
	treeL := NewSegTree(numY) // Indexed by Y-rank, stores X-coordinate

	usedCols := make([]bool, numX+1)
	usedRows := make([]bool, numY+1)

	for _, cur := range qs {
		rX, rY := xMap[cur.x], yMap[cur.y]
		if usedCols[rX] || usedRows[rY] {
			fmt.Fprintln(out, 0)
			continue
		}

		if cur.dir == 'U' {
			usedCols[rX] = true
			barrierY := 0
			if rY > 1 {
				// Find horizontal barrier (L-cut) above this row
				// We seek max rank y' < rY such that treeL[y'] <= cur.x
				idx := treeL.Query(1, 1, numY, rY-1, cur.x)
				if idx != -1 {
					barrierY = uY[idx-1]
				}
			}
			fmt.Fprintln(out, cur.y-barrierY)
			// Update vertical barrier (U-cut) at this column
			treeU.Update(1, 1, numX, rX, barrierY+1)
		} else {
			usedRows[rY] = true
			barrierX := 0
			if rX > 1 {
				// Find vertical barrier (U-cut) to the left of this column
				// We seek max rank x' < rX such that treeU[x'] <= cur.y
				idx := treeU.Query(1, 1, numX, rX-1, cur.y)
				if idx != -1 {
					barrierX = uX[idx-1]
				}
			}
			fmt.Fprintln(out, cur.x-barrierX)
			// Update horizontal barrier (L-cut) at this row
			treeL.Update(1, 1, numY, rY, barrierX+1)
		}
	}
}
```