import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: src/cplib/tmpl/sheep.nim
ImportExpand "cplib/tmpl/sheep" <=== "when not declared CPLIB_TMPL_SHEEP:\n    const CPLIB_TMPL_SHEEP* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import heapqueue\n    import streams\n    import deques\n    import bitops\n    import std/lenientops\n    import options\n    #入力系\n    proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n    proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n    proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n    proc si(): string {.inline.} =\n        result = \"\"\n        var c: char\n        while true:\n            c = getchar()\n            if c == ' ' or c == '\\n' or c == '\\255':\n                break\n            result &= c\n    #chmin,chmax\n    template `max=`(x, y) = x = max(x, y)\n    template `min=`(x, y) = x = min(x, y)\n    proc chmin[T](x: var T, y: T):bool=\n        if x > y:\n            x = y\n            return true\n        return false\n    proc chmax[T](x: var T, y: T):bool=\n        if x < y:\n            x = y\n            return true\n        return false\n    #bit演算\n    proc `%`*(x: int, y: int): int =\n        result = x mod y\n        if y > 0 and result < 0: result += y\n        if y < 0 and result > 0: result += y\n    proc `//`*(x: int, y: int): int{.inline.} =\n        result = x div y\n        if y > 0 and result * y > x: result -= 1\n        if y < 0 and result * y < x: result -= 1\n    proc `%=`(x: var int, y: int): void = x = x%y\n    proc `//=`(x: var int, y: int): void = x = x//y\n    proc `**`(x: int, y: int): int = x^y\n    proc `**=`(x: var int, y: int): void = x = x^y\n    proc `^`(x: int, y: int): int = x xor y\n    proc `|`(x: int, y: int): int = x or y\n    proc `&`(x: int, y: int): int = x and y\n    proc `>>`(x: int, y: int): int = x shr y\n    proc `<<`(x: int, y: int): int = x shl y\n    proc `~`(x: int): int = not x\n    proc `^=`(x: var int, y: int): void = x = x ^ y\n    proc `&=`(x: var int, y: int): void = x = x & y\n    proc `|=`(x: var int, y: int): void = x = x | y\n    proc `>>=`(x: var int, y: int): void = x = x >> y\n    proc `<<=`(x: var int, y: int): void = x = x << y\n    proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n    #便利な変換\n    proc `!`(x: char, a = '0'): int = int(x)-int(a)\n    #定数\n    when not declared CPLIB_UTILS_CONSTANTS:\n        const CPLIB_UTILS_CONSTANTS* = 1\n        const INF32*: int32 = 1001000027.int32\n        const INF64*: int = int(3300300300300300491)\n    \n    const INF = INF64\n    #converter\n\n    #range\n    iterator range(start: int, ends: int, step: int): int =\n        var i = start\n        if step < 0:\n            while i > ends:\n                yield i\n                i += step\n        elif step > 0:\n            while i < ends:\n                yield i\n                i += step\n    iterator range(ends: int): int = (for i in 0..<ends: yield i)\n    iterator range(start: int, ends: int): int = (for i in\n            start..<ends: yield i)\n\n    #joinが非stringでめちゃくちゃ遅いやつのパッチ\n    proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n    proc dump[T](arr:seq[seq[T]])=\n        for i in 0..<len(arr):\n            echo arr[i]\n\n    proc sum(slice:HSlice[int,int]):int=\n        return (slice.a+slice.b)*len(slice)//2\n    \n    proc `<`[T](l,r:seq[T]):bool=\n        for i in 0..<min(len(l),len(r)):\n            if l[i] > r[i]:\n                return false\n            elif l[i] < r[i]:\n                return true\n        return len(l) < len(r)"
# source: src/cplib/collections/wordsizetree.nim
ImportExpand "cplib/collections/wordsizetree" <=== "when not declared CPLIB_COLLECTIONS_WORD_SIZE_TREE:\n    const CPLIB_COLLECTIONS_WORD_SIZE_TREE* = 1\n    import bitops\n    type WordsizeTree = object\n        A0 : uint\n        A1 : array[64,uint]\n        A2 : array[64*64,uint]\n        A3 : array[64*64*64,uint]\n\n    proc initWordsizeTree*():WordsizeTree=\n        discard\n\n    proc initWordsizeTree*(v:seq[bool]):WordsizeTree=\n        for i in 0..<len(v):\n            if v[i]: result.A3[i shr 6] = result.A3[i shr 6] or (1u shl (i and(0b111111)))\n        for i in 0..<((len(v)+(63)) shr 6):\n            if result.A3[i] != 0:result.A2[i shr 6] = result.A2[i shr 6] or (1u shl (i and(0b111111)))\n        for i in 0..<((len(v)+(64*64-1)) shr 12):\n            if result.A2[i] != 0:result.A1[i shr 6] = result.A1[i shr 6] or (1u shl (i and(0b111111)))\n        for i in 0..<((len(v)+(64*64*64-1)) shr 18):\n            if result.A1[i] != 0:result.A0 = result.A0 or (1u shl (i and(0b111111)))\n\n\n    proc incl*(self:var WordsizeTree,x:int)=\n        var y = x and (0b111111)\n        var x = x shr 6\n        self.A3[x] = self.A3[x] or (1u shl y)\n        y = x and (0b111111)\n        x = x shr 6\n        self.A2[x] = self.A2[x] or (1u shl y)\n        y = x and (0b111111)\n        x = x shr 6\n        self.A1[x] = self.A1[x] or (1u shl y)\n        y = x and (0b111111)\n        x = x shr 6\n        self.A0 = self.A0 or (1u shl y)\n\n    proc `[]`*(self:var WordsizeTree,x:int):bool=\n        var y = x and (0b111111)\n        var x = x shr 6\n        return (self.A3[x] and (1u shl y)) != 0\n\n    proc excl*(self:var WordsizeTree,x:int)=\n        if self[x]:\n            var y = x and (0b111111)\n            var x = x shr 6\n            self.A3[x].clearBit(y)\n            if self.A3[x] != 0:return\n            y = x and (0b111111)\n            x = x shr 6\n            self.A2[x].clearBit(y)\n            if self.A2[x] != 0:return\n            y = x and (0b111111)\n            x = x shr 6\n            self.A1[x].clearBit(y)\n            if self.A1[x] != 0:return\n            y = x and (0b111111)\n            x = x shr 6\n            self.A0.clearBit(y)\n\n\n    proc ge*(self:var WordsizeTree,x:int):int=\n        var y = x and (0b111111)\n        var x = x shr 6\n        var t = self.A3[x] and (bitnot(0u) shl y)\n        if t != 0:\n            return (x shl 6) or (t.firstSetBit()-1)\n        \n        y = (x and (0b111111))+1\n        x = x shr 6\n        t = self.A2[x] and (bitnot(0u) shl y)\n        if y != 64 and t != 0:\n            x = (x shl 6) or (t.firstSetBit()-1)\n            return (x shl 6) or (self.A3[x].firstSetBit()-1)\n        \n        y = (x and (0b111111))+1\n        x = x shr 6\n        t = self.A1[x] and (bitnot(0u) shl y)\n        if y != 64 and t != 0:\n            x = (x shl 6) or (t.firstSetBit()-1)\n            x = (x shl 6) or (self.A2[x].firstSetBit()-1)\n            return (x shl 6) or (self.A3[x].firstSetBit()-1)\n        y = (x and (0b111111))+1\n        x = x shr 6\n        t = self.A0 and (bitnot(0u) shl y)\n        if y != 64 and t != 0:\n            x = (t.firstSetBit()-1)\n            x = (x shl 6) or (self.A1[x].firstSetBit()-1)\n            x = (x shl 6) or (self.A2[x].firstSetBit()-1)\n            return (x shl 6) or (self.A3[x].firstSetBit()-1)\n        return -1\n\n    proc le*(self:var WordsizeTree,x:int):int=\n        var y = 64-(x and (0b111111))-1\n        var x = x shr 6\n        var t = self.A3[x] and (bitnot(0u) shr y)\n        if t != 0:\n            return (x shl 6) or (t.fastLog2())\n        y = 64-((x and (0b111111)))\n        x = x shr 6\n        t = self.A2[x] and (bitnot(0u) shr y)\n        if y != 64 and t != 0:\n            x = (x shl 6) or (t.fastLog2())\n            return (x shl 6) or (self.A3[x].fastLog2())\n        y = 64-((x and (0b111111)))\n        x = x shr 6\n        t = self.A1[x] and (bitnot(0u) shr y)\n        if y != 64 and t != 0:\n            x = (x shl 6) or (t.fastLog2())\n            x = (x shl 6) or (self.A2[x].fastLog2())\n            return (x shl 6) or (self.A3[x].fastLog2())\n        y = 64-((x and (0b111111)))\n        x = x shr 6\n        t = self.A0 and (bitnot(0u) shr y)\n        if y != 64 and t != 0:\n            x = (t.fastLog2())\n            x = (x shl 6) or (self.A1[x].fastLog2())\n            x = (x shl 6) or (self.A2[x].fastLog2())\n            return (x shl 6) or (self.A3[x].fastLog2())\n        return -1"
# source: src/cplib/utils/mo.nim
ImportExpand "cplib/utils/mo" <=== "when not declared CPLIB_UTILS_MO:\n    #{.checks: off.}\n    const CPLIB_UTILS_MO* = 1\n    import std/math\n    import std/algorithm\n    type Mo* = object\n        width*: int\n        N, Q: int\n        qli: seq[seq[int]]\n        size: int\n\n    proc initMo*(N, Q: int, width = max(1, int(1.0 * float(N) / max(1.0, sqrt(float(Q) * 2.0 / 3.0))))): Mo =\n        result.width = width\n        result.N = N\n        result.Q = Q\n        let qlisize = N div width + 1\n        result.qli = newSeq[seq[int]](qlisize)\n\n    proc insert*(self: var Mo, l, r: int) =\n        self.qli[l div self.width].add((r shl 40) or ((l) shl 20) or self.size)\n        self.size += 1\n\n    proc run*[AL, AR, DL, DR, REM](self: var Mo, add_left: AL, add_right: AR, delete_left: DL, delete_right: DR, rem: REM) =\n        var nl = 0\n        var nr = 0\n        const mask2 = ((1 shl 20)-1) shl 20\n        const mask3 = ((1 shl 20)-1)\n        for i in 0..<len(self.qli):\n            if len(self.qli[i]) == 0:\n                continue\n            sort(self.qli[i])\n            if (i and 1) == 1:\n                reverse(self.qli[i])\n            for x in self.qli[i]:\n                let ri = x shr 40\n                let li = (x and mask2) shr 20\n                let idx = x and mask3\n                while nl > li: nl.dec; add_left(nl)\n                while nr < ri: add_right(nr); nr.inc\n                while nl < li: delete_left(nl); nl.inc\n                while nr > ri: nr.dec; delete_right(nr)\n                rem(idx)\n"



var N,Q = ii()
var A = lii(N)
var cmp : seq[(int,int)]
for i in range(N):
    cmp.add((A[i],i))
cmp.sort()

var rv = newseqwith(N,-1)

for i in range(N):
    rv[cmp[i][1]] = i

var mos = initMo(N,Q)
var querys : seq[(int,int,int,char)]
for _ in range(Q):
    var L,R,X = ii()
    var c = si()[0]
    L-=1
    R-=1
    querys.add((L,R,X,c))
    mos.insert(L,R+1)

var st = initWordsizeTree()
var st2 = initWordsizeTree()
var cnt = newseqwith(10**7,0)

proc add_lr(l,r:int)=
    var L = cmp[l][0]
    var R = cmp[r][0]
    if cnt[R-L] == 0:
        st2.incl(R-L)
    cnt[R-L] += 1

proc del_lr(l,r:int)=
    var L = cmp[l][0]
    var R = cmp[r][0]
    if cnt[R-L] == 1:
        st2.excl(R-L)
    cnt[R-L] -= 1

proc ad(i:int)=
    var x = rv[i]
    var L = st.le(x)
    var R = st.ge(x)
    if L != -1 and R != -1:
        del_lr(L,R)
        add_lr(L,x)
        add_lr(x,R)
    elif R != -1:
        add_lr(x,R)
    elif L != -1:
        add_lr(L,x)
    st.incl(x)

proc de(i:int)=
    var x = rv[i]
    st.excl(x)
    var L = st.le(x)
    var R = st.ge(x)
    if L != -1 and R != -1:
        add_lr(L,R)
        del_lr(L,x)
        del_lr(x,R)
    elif R != -1:
        del_lr(x,R)
    elif L != -1:
        del_lr(L,x)

var ans = newseqwith(Q,-1)

proc memo(qi:int)=
    var (L,R,X,c) = querys[qi]
    if c == 'L':
        ans[qi] = st2.le(X)
    else:
        ans[qi] = st2.ge(X)


mos.run(ad,ad,de,de,memo)

echo ans.join("\n")