use proconio::marker::*;
use proconio::*;

#[fastout]
fn run() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        ask: [(Usize1, usize, usize, char); q],
    }
    let mut z = (0..n).collect::<Vec<_>>();
    z.sort_by_key(|z| a[*z]);
    let mut iz = vec![0; n];
    for i in 0..n {
        iz[z[i]] = i;
    }
    let mut za = vec![0; n];
    for i in 0..n {
        za[i] = a[z[i]];
    }
    let mut set = FastSet::new(n);
    let mut hist = vec![0i32; 10000000];
    let mut c = FastSet::new(10000000);
    let mut ans = vec![-1; q];
    let mut s = 0;
    let mut t = 0;
    let batch = (1..).find(|&i| i * i > q).unwrap();
    let mut ord = (0..q).collect::<Vec<_>>();
    ord.sort_by_key(|x| ask[*x].0);
    for (i, ord) in ord.chunks_mut(batch).enumerate() {
        ord.sort_by_key(|x| ask[*x].1);
        if i % 2 == 1 {
            ord.reverse();
        }
        for &k in ord.iter() {
            let (l, r, x, op) = ask[k];
            for i in (l..s).chain(t..r) {
                let pos = iz[i];
                let (p, q) = (set.prev(pos), set.next(pos));
                if let (Some(p), Some(q)) = (p, q) {
                    let d = za[q] - za[p];
                    remove(d, &mut hist, &mut c);
                }
                if let Some(p) = p {
                    let d = a[i] - za[p];
                    insert(d, &mut hist, &mut c);
                }
                if let Some(p) = q {
                    let d = za[p] - a[i];
                    insert(d, &mut hist, &mut c);
                }
                set.insert(pos);
            }
            for i in (s..l).chain(r..t) {
                let pos = iz[i];
                set.remove(pos);
                let (p, q) = (set.prev(pos), set.next(pos));
                if let Some(p) = p {
                    let d = a[i] - za[p];
                    remove(d, &mut hist, &mut c);
                }
                if let Some(p) = q {
                    let d = za[p] - a[i];
                    remove(d, &mut hist, &mut c);
                }
                if let (Some(p), Some(q)) = (p, q) {
                    let d = za[q] - za[p];
                    insert(d, &mut hist, &mut c);
                }
            }
            s = l;
            t = r;
            if op == 'L' {
                if let Some(q) = c.prev(x) {
                    ans[k] = q as i32;
                }
            } else {
                if let Some(q) = c.next(x) {
                    ans[k] = q as i32;
                }
            }
        }
    }
    for a in ans {
        println!("{}", a);
    }
}

fn insert(d: usize, hist: &mut [i32], c: &mut FastSet) {
    hist[d] += 1;
    if hist[d] == 1 {
        c.insert(d);
    }
}

fn remove(d: usize, hist: &mut [i32], c: &mut FastSet) {
    hist[d] -= 1;
    if hist[d] == 0 {
        c.remove(d);
    }
}

fn main() {
    run();
}

pub struct FastSet {
    size: usize,
    seg: Vec<Vec<usize>>,
}

impl FastSet {
    pub fn build<I>(size: usize, init: I) -> Self
    where
        I: Iterator<Item = usize>,
    {
        assert!(size > 0);
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        let mut data = vec![0; (n + w - 1) / w];
        for x in init {
            assert!(x < size);
            data[x / w] |= 1 << (x % w);
        }
        seg.push(data);
        while n > 1 {
            n = (n + w - 1) / w;
            let d = seg
                .last()
                .unwrap()
                .chunks(w)
                .map(|a| {
                    a.iter()
                        .enumerate()
                        .filter(|p| *p.1 > 0)
                        .fold(0, |s, a| s | (1 << a.0))
                })
                .collect::<Vec<_>>();
            seg.push(d);
        }
        Self { size, seg }
    }
    pub fn new(size: usize) -> Self {
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        while {
            let m = (n + w - 1) / w;
            seg.push(vec![0; m]);
            n = m;
            n > 1
        } {}
        Self { size, seg }
    }
    pub fn insert(&mut self, mut x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) == 1 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] |= 1 << (x % w);
            x /= w;
        }
        true
    }
    pub fn remove(&mut self, mut x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) & 1 == 0 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] &= !(1 << (x % w));
            if seg[x / w] != 0 {
                break;
            }
            x /= w;
        }
        true
    }
    pub fn contains(&self, x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        self.seg[0][x / w] >> (x % w) & 1 == 1
    }
    pub fn next(&self, mut x: usize) -> Option<usize> {
        if x >= self.size {
            return None;
        }
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            if x / w >= s.len() {
                return None;
            }
            let d = s[x / w] >> (x % w);
            if d == 0 {
                x = x / w + 1;
                continue;
            }
            x += d.trailing_zeros() as usize;
            for seg in seg[..i].iter().rev() {
                let k = seg[x].trailing_zeros() as usize;
                x = w * x + k;
            }
            return Some(x);
        }
        None
    }
    pub fn prev(&self, mut x: usize) -> Option<usize> {
        x = x.min(self.size - 1);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            let d = s[x / w] << (w - 1 - x % w);
            if d == 0 {
                if x < w {
                    break;
                }
                x = x / w - 1;
                continue;
            }
            x -= d.leading_zeros() as usize;
            for seg in seg[..i].iter().rev() {
                let k = w - 1 - seg[x].leading_zeros() as usize;
                x = w * x + k;
            }
            return Some(x);
        }
        None
    }
}