#include <bits/stdc++.h>
using namespace std;

/*
    問題の管理対象
    ----------------
    現在区間 [curL, curR] に対して

    1. 各値の出現回数 freq[id]
    2. 出現回数 >= 1 の distinct 値の集合 active
    3. active を昇順に並べたときの隣接差 multiset gaps
    4. 重複によって生じる差 0 の個数 zeroGapCount

    を管理する。

    クエリ
    - type == 'L' : C の要素で X 以下の最大値
    - type == 'R' : C の要素で X 以上の最小値
*/

/*------------------------------------------------------------
 | Hilbert Order
 *-----------------------------------------------------------*/
static long long hilbert_order(int x, int y, int pow = 21, int rot = 0) {
    if (pow == 0) return 0;
    int hpow = 1 << (pow - 1);

    int seg = (x < hpow)
        ? ((y < hpow) ? 0 : 3)
        : ((y < hpow) ? 1 : 2);

    seg = (seg + rot) & 3;
    static const int rotate_delta[4] = {3, 0, 0, 1};

    int nx = x & (x ^ hpow);
    int ny = y & (y ^ hpow);
    int nrot = (rot + rotate_delta[seg]) & 3;

    long long sub_size = 1LL << (2 * pow - 2);
    long long ans = 1LL * seg * sub_size;
    long long add = hilbert_order(nx, ny, pow - 1, nrot);

    ans += (seg == 1 || seg == 2) ? add : (sub_size - add - 1);
    return ans;
}

/*------------------------------------------------------------
 | 64分木系の高速順序集合
 | 0..n-1 の整数について insert / erase / contains / next / prev
 *-----------------------------------------------------------*/
struct FastSet {
    int n;
    vector<vector<unsigned long long>> seg;

    FastSet() : n(0) {}
    explicit FastSet(int n_) { init(n_); }

    void init(int n_) {
        n = n_;
        seg.clear();
        seg.push_back(vector<unsigned long long>((n + 63) >> 6, 0ULL));
        while (seg.back().size() > 1) {
            int m = (int)seg.back().size();
            seg.push_back(vector<unsigned long long>((m + 63) >> 6, 0ULL));
        }
    }

    bool contains(int x) const {
        return (seg[0][x >> 6] >> (x & 63)) & 1ULL;
    }

    void insert(int x) {
        for (int h = 0; h < (int)seg.size(); h++) {
            seg[h][x >> 6] |= 1ULL << (x & 63);
            x >>= 6;
        }
    }

    void erase(int x) {
        for (int h = 0; h < (int)seg.size(); h++) {
            auto &block = seg[h][x >> 6];
            block &= ~(1ULL << (x & 63));
            if (block) break;
            x >>= 6;
        }
    }

    // x 以上の最小の存在要素。なければ n を返す
    int next(int x) const {
        if (x < 0) x = 0;
        if (x >= n) return n;

        for (int h = 0; h < (int)seg.size(); h++) {
            int i = x >> 6;
            if (i >= (int)seg[h].size()) break;

            unsigned long long d = seg[h][i] >> (x & 63);
            if (d == 0) {
                i++;
                while (i < (int)seg[h].size() && seg[h][i] == 0) i++;
                if (i == (int)seg[h].size()) return n;
                x = i << 6;
            } else {
                x += __builtin_ctzll(d);
            }

            for (int g = h - 1; g >= 0; g--) {
                x <<= 6;
                unsigned long long d2 = seg[g][x >> 6];
                x += __builtin_ctzll(d2);
            }
            return x;
        }
        return n;
    }

    // x 以下の最大の存在要素。なければ -1 を返す
    int prev(int x) const {
        if (x < 0) return -1;
        if (x >= n) x = n - 1;

        for (int h = 0; h < (int)seg.size(); h++) {
            int i = x >> 6;
            if (i < 0) return -1;

            unsigned long long d;
            if ((x & 63) == 63) {
                d = seg[h][i];
            } else {
                d = seg[h][i] & ((1ULL << ((x & 63) + 1)) - 1);
            }

            if (d == 0) {
                i--;
                while (i >= 0 && seg[h][i] == 0) i--;
                if (i < 0) return -1;
                x = (i << 6) + 63;
            } else {
                x = (i << 6) + 63 - __builtin_clzll(d);
            }

            for (int g = h - 1; g >= 0; g--) {
                x <<= 6;
                int block = x >> 6;
                unsigned long long d2 = seg[g][block];
                x += 63 - __builtin_clzll(d2);
            }
            return x;
        }
        return -1;
    }
};

/*------------------------------------------------------------
 | Query
 *-----------------------------------------------------------*/
struct Query {
    int l, r, x, id;
    char type;
    long long ord;
};

/*------------------------------------------------------------
 | 1個だけ erase する補助
 *-----------------------------------------------------------*/
static inline void erase_one(multiset<int>& ms, int value) {
    auto it = ms.find(value);
    if (it != ms.end()) ms.erase(it);
}

/*------------------------------------------------------------
 | 現在区間の状態管理
 *-----------------------------------------------------------*/
class RangeManager {
public:
    RangeManager(const vector<int>& compressedToValue, int compressedSize)
        : values(compressedToValue),
          freq(compressedSize, 0),
          active(compressedSize),
          zeroGapCount(0) {}

    void addCompressedValue(int id) {
        // すでに存在する値なら、差 0 が1個増えるだけ
        if (freq[id] >= 1) {
            freq[id]++;
            zeroGapCount++;
            return;
        }

        // 初出現: active に入れる
        int rightId = active.next(id);
        int leftId = active.prev(id);

        bool hasLeft = (leftId != -1);
        bool hasRight = (rightId != (int)values.size());

        int x = values[id];

        if (hasLeft && hasRight) {
            int leftValue = values[leftId];
            int rightValue = values[rightId];
            erase_one(gaps, rightValue - leftValue);
            gaps.insert(x - leftValue);
            gaps.insert(rightValue - x);
        } else if (hasLeft) {
            int leftValue = values[leftId];
            gaps.insert(x - leftValue);
        } else if (hasRight) {
            int rightValue = values[rightId];
            gaps.insert(rightValue - x);
        }

        active.insert(id);
        freq[id] = 1;
    }

    void removeCompressedValue(int id) {
        // まだ複数個あるなら、差 0 が1個減るだけ
        if (freq[id] >= 2) {
            freq[id]--;
            zeroGapCount--;
            return;
        }

        // 最後の1個を消す: active から除去
        int leftId = active.prev(id - 1);
        int rightId = active.next(id + 1);

        bool hasLeft = (leftId != -1);
        bool hasRight = (rightId != (int)values.size());

        int x = values[id];

        if (hasLeft && hasRight) {
            int leftValue = values[leftId];
            int rightValue = values[rightId];
            erase_one(gaps, x - leftValue);
            erase_one(gaps, rightValue - x);
            gaps.insert(rightValue - leftValue);
        } else if (hasLeft) {
            int leftValue = values[leftId];
            erase_one(gaps, x - leftValue);
        } else if (hasRight) {
            int rightValue = values[rightId];
            erase_one(gaps, rightValue - x);
        }

        active.erase(id);
        freq[id] = 0;
    }

    int answer(int X, char type) const {
        if (type == 'L') {
            int best = -1;

            // X >= 1 なので 0 は常に候補になりうる
            if (zeroGapCount > 0) best = 0;

            auto it = gaps.upper_bound(X);
            if (it != gaps.begin()) {
                --it;
                best = max(best, *it);
            }
            return best;
        } else {
            auto it = gaps.lower_bound(X);
            if (it == gaps.end()) return -1;
            return *it;
        }
    }

private:
    const vector<int>& values;   // 圧縮ID -> 元の値
    vector<int> freq;
    FastSet active;              // 現在存在する distinct 値の圧縮ID集合
    multiset<int> gaps;          // distinct 値間の隣接差
    int zeroGapCount;            // 差0の個数
};

/*------------------------------------------------------------
 | main
 *-----------------------------------------------------------*/
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // 座標圧縮
    vector<int> sortedValues = A;
    sort(sortedValues.begin(), sortedValues.end());
    sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()), sortedValues.end());

    int M = (int)sortedValues.size();

    vector<int> compressedA(N);
    for (int i = 0; i < N; i++) {
        compressedA[i] = lower_bound(sortedValues.begin(), sortedValues.end(), A[i]) - sortedValues.begin();
    }

    // クエリ読み込み
    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        int L, R, X;
        char c;
        cin >> L >> R >> X >> c;
        --L;
        --R;
        queries[i] = {L, R, X, i, c, hilbert_order(L, R)};
    }

    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.ord < b.ord;
    });

    RangeManager manager(sortedValues, M);
    vector<int> answers(Q, -1);

    int curL = 0;
    int curR = -1;

    for (const auto& q : queries) {
        while (curL > q.l) manager.addCompressedValue(compressedA[--curL]);
        while (curR < q.r) manager.addCompressedValue(compressedA[++curR]);
        while (curL < q.l) manager.removeCompressedValue(compressedA[curL++]);
        while (curR > q.r) manager.removeCompressedValue(compressedA[curR--]);

        answers[q.id] = manager.answer(q.x, q.type);
    }

    for (int i = 0; i < Q; i++) {
        cout << answers[i] << '\n';
    }

    return 0;
}