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

struct Fenwick {
    int n = 0;
    vector<int> bit;

    void build(const vector<int>& a) {
        n = (int)a.size();
        bit.assign(n + 1, 0);

        for (int i = 0; i < n; ++i) {
            bit[i + 1] += a[i];

            int parent = i + 1 + ((i + 1) & -(i + 1));
            if (parent <= n) {
                bit[parent] += bit[i + 1];
            }
        }
    }

    void add(int index, int value) {
        for (int i = index + 1; i <= n; i += i & -i) {
            bit[i] += value;
        }
    }

    // Tổng kích thước các block có chỉ số < index.
    int prefixBefore(int index) const {
        int result = 0;

        for (int i = index; i > 0; i -= i & -i) {
            result += bit[i];
        }

        return result;
    }

    // Trả về block chứa phần tử thứ k, với k đánh số từ 1.
    int kth(int k) const {
        int index = 0;
        int currentSum = 0;

        int step = 1;
        while ((step << 1) <= n) {
            step <<= 1;
        }

        for (; step > 0; step >>= 1) {
            int nextIndex = index + step;

            if (nextIndex <= n &&
                currentSum + bit[nextIndex] < k) {
                index = nextIndex;
                currentSum += bit[nextIndex];
            }
        }

        return index;
    }
};

struct DynamicOrder {
    static constexpr int BLOCK_SIZE = 128;

    struct Block {
        vector<int> elements;
        int order = -1;
    };

    int n;

    vector<Block*> blocks;
    vector<Block*> owner;
    vector<int> positionInBlock;

    Fenwick fenwick;

    DynamicOrder(const vector<int>& sequence, int numberOfElements)
        : n(numberOfElements),
          owner(n + 1),
          positionInBlock(n + 1) {
        for (int left = 0; left < n; left += BLOCK_SIZE) {
            int right = min(n, left + BLOCK_SIZE);

            Block* block = new Block();
            block->elements.reserve(2 * BLOCK_SIZE + 1);

            for (int i = left; i < right; ++i) {
                int value = sequence[i];

                owner[value] = block;
                positionInBlock[value] =
                    (int)block->elements.size();

                block->elements.push_back(value);
            }

            block->order = (int)blocks.size();
            blocks.push_back(block);
        }

        rebuildFenwick();
    }

    ~DynamicOrder() {
        for (Block* block : blocks) {
            delete block;
        }
    }

    void rebuildFenwick() {
        vector<int> sizes(blocks.size());

        for (int i = 0; i < (int)blocks.size(); ++i) {
            blocks[i]->order = i;
            sizes[i] = (int)blocks[i]->elements.size();
        }

        fenwick.build(sizes);
    }

    // true khi hạng an toàn của x nhỏ hơn hạng của y.
    bool before(int x, int y) const {
        if (owner[x] == owner[y]) {
            return positionInBlock[x] < positionInBlock[y];
        }

        return owner[x]->order < owner[y]->order;
    }

    // Phần tử có hạng lớn hơn, tức kém an toàn hơn.
    int later(int x, int y) const {
        if (x == -1) {
            return y;
        }

        if (y == -1) {
            return x;
        }

        return before(x, y) ? y : x;
    }

    bool atLeast(int x, int threshold) const {
        return !before(x, threshold);
    }

    void eraseFromBlock(Block* block, int index) {
        block->elements.erase(block->elements.begin() + index);

        for (int i = index;
             i < (int)block->elements.size();
             ++i) {
            positionInBlock[block->elements[i]] = i;
        }
    }

    void insertIntoBlock(Block* block, int index, int value) {
        block->elements.insert(
            block->elements.begin() + index,
            value
        );

        for (int i = index;
             i < (int)block->elements.size();
             ++i) {
            int element = block->elements[i];

            owner[element] = block;
            positionInBlock[element] = i;
        }
    }

    void splitIfNeeded(Block* block) {
        if ((int)block->elements.size() <=
            2 * BLOCK_SIZE) {
            return;
        }

        int blockIndex = block->order;
        int middle = (int)block->elements.size() / 2;

        Block* newBlock = new Block();
        newBlock->elements.reserve(2 * BLOCK_SIZE + 1);

        newBlock->elements.assign(
            block->elements.begin() + middle,
            block->elements.end()
        );

        block->elements.erase(
            block->elements.begin() + middle,
            block->elements.end()
        );

        for (int i = 0;
             i < (int)newBlock->elements.size();
             ++i) {
            int element = newBlock->elements[i];

            owner[element] = newBlock;
            positionInBlock[element] = i;
        }

        blocks.insert(
            blocks.begin() + blockIndex + 1,
            newBlock
        );

        rebuildFenwick();
    }

    // Đưa x tới hạng rank, rank đánh số từ 1.
    void moveToRank(int x, int rank) {
        Block* sourceBlock = owner[x];
        int sourceBlockIndex = sourceBlock->order;
        int sourcePosition = positionInBlock[x];

        eraseFromBlock(sourceBlock, sourcePosition);
        fenwick.add(sourceBlockIndex, -1);

        int targetBlockIndex = fenwick.kth(rank);
        int elementsBefore =
            fenwick.prefixBefore(targetBlockIndex);

        int targetPosition =
            rank - elementsBefore - 1;

        Block* targetBlock = blocks[targetBlockIndex];

        insertIntoBlock(
            targetBlock,
            targetPosition,
            x
        );

        fenwick.add(targetBlockIndex, 1);

        splitIfNeeded(targetBlock);
    }
};

struct SegmentTree {
    int n;
    int size;

    vector<int> tree;
    DynamicOrder* order;

    SegmentTree(int numberOfPositions, DynamicOrder* orderStructure)
        : n(numberOfPositions), order(orderStructure) {
        size = 1;

        while (size < n) {
            size <<= 1;
        }

        tree.assign(size << 1, -1);

        for (int i = 1; i <= n; ++i) {
            tree[size + i - 1] = i;
        }

        for (int node = size - 1; node >= 1; --node) {
            tree[node] = order->later(
                tree[node << 1],
                tree[node << 1 | 1]
            );
        }
    }

    void refresh(int position) {
        int node = size + position - 1;

        for (node >>= 1; node > 0; node >>= 1) {
            tree[node] = order->later(
                tree[node << 1],
                tree[node << 1 | 1]
            );
        }
    }

    int rangeMaximum(int left, int right) const {
        int leftResult = -1;
        int rightResult = -1;

        int l = size + left - 1;
        int r = size + right - 1;

        while (l <= r) {
            if (l & 1) {
                leftResult =
                    order->later(leftResult, tree[l]);
                ++l;
            }

            if (!(r & 1)) {
                rightResult =
                    order->later(tree[r], rightResult);
                --r;
            }

            l >>= 1;
            r >>= 1;
        }

        return order->later(leftResult, rightResult);
    }

    int findLastRecursive(
        int node,
        int nodeLeft,
        int nodeRight,
        int queryLeft,
        int queryRight,
        int threshold
    ) const {
        if (nodeRight < queryLeft ||
            queryRight < nodeLeft ||
            tree[node] == -1 ||
            !order->atLeast(tree[node], threshold)) {
            return -1;
        }

        if (nodeLeft == nodeRight) {
            return nodeLeft;
        }

        int middle = (nodeLeft + nodeRight) >> 1;

        int result = findLastRecursive(
            node << 1 | 1,
            middle + 1,
            nodeRight,
            queryLeft,
            queryRight,
            threshold
        );

        if (result != -1) {
            return result;
        }

        return findLastRecursive(
            node << 1,
            nodeLeft,
            middle,
            queryLeft,
            queryRight,
            threshold
        );
    }

    int findFirstRecursive(
        int node,
        int nodeLeft,
        int nodeRight,
        int queryLeft,
        int queryRight,
        int threshold
    ) const {
        if (nodeRight < queryLeft ||
            queryRight < nodeLeft ||
            tree[node] == -1 ||
            !order->atLeast(tree[node], threshold)) {
            return -1;
        }

        if (nodeLeft == nodeRight) {
            return nodeLeft;
        }

        int middle = (nodeLeft + nodeRight) >> 1;

        int result = findFirstRecursive(
            node << 1,
            nodeLeft,
            middle,
            queryLeft,
            queryRight,
            threshold
        );

        if (result != -1) {
            return result;
        }

        return findFirstRecursive(
            node << 1 | 1,
            middle + 1,
            nodeRight,
            queryLeft,
            queryRight,
            threshold
        );
    }

    int findLast(
        int left,
        int right,
        int threshold
    ) const {
        if (left > right) {
            return -1;
        }

        return findLastRecursive(
            1,
            1,
            size,
            left,
            right,
            threshold
        );
    }

    int findFirst(
        int left,
        int right,
        int threshold
    ) const {
        if (left > right) {
            return -1;
        }

        return findFirstRecursive(
            1,
            1,
            size,
            left,
            right,
            threshold
        );
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("vi.INP" , "r" , stdin);
    freopen("vi.OUT" , "w" , stdout);
    
    int subtask;
    cin >> subtask;

    int n, q, favourite;
    cin >> n >> q >> favourite;

    vector<int> safety(n + 1);
    vector<int> positionAtRank(n);

    for (int position = 1; position <= n; ++position) {
        cin >> safety[position];
        positionAtRank[safety[position] - 1] = position;
    }

    DynamicOrder order(positionAtRank, n);
    SegmentTree segmentTree(n, &order);

    while (q--) {
        char type;
        cin >> type;

        if (type == 'U') {
            int position, newRank;
            cin >> position >> newRank;

            /*
            Sau cập nhật, quan hệ thứ tự giữa mọi cặp vị trí
            không chứa position vẫn giữ nguyên. Vì vậy chỉ cần
            cập nhật đường đi của position trên segment tree.
            */
            order.moveToRank(position, newRank);
            segmentTree.refresh(position);
        } else {
            int position;
            cin >> position;

            if (position == favourite) {
                cout << 1 << '\n';
                continue;
            }

            if (position > favourite) {
                /*
                Hạng lớn nhất trên đoạn từ favourite + 1
                tới position.
                */
                int threshold = segmentTree.rangeMaximum(
                    favourite + 1,
                    position
                );

                /*
                Vị trí gần favourite nhất ở phía trái có
                hạng không nhỏ hơn threshold.
                */
                int blocker = segmentTree.findLast(
                    1,
                    favourite - 1,
                    threshold
                );

                int oppositeSeatsBefore;

                if (blocker == -1) {
                    oppositeSeatsBefore = favourite - 1;
                } else {
                    oppositeSeatsBefore =
                        favourite - blocker - 1;
                }

                cout << position - favourite + 1
                             + oppositeSeatsBefore
                     << '\n';
            } else {
                int threshold = segmentTree.rangeMaximum(
                    position,
                    favourite - 1
                );

                int blocker = segmentTree.findFirst(
                    favourite + 1,
                    n,
                    threshold
                );

                int oppositeSeatsBefore;

                if (blocker == -1) {
                    oppositeSeatsBefore = n - favourite;
                } else {
                    oppositeSeatsBefore =
                        blocker - favourite - 1;
                }

                cout << favourite - position + 1
                             + oppositeSeatsBefore
                     << '\n';
            }
        }
    }

    return 0;
}