#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;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgRmVud2ljayB7CiAgICBpbnQgbiA9IDA7CiAgICB2ZWN0b3I8aW50PiBiaXQ7CgogICAgdm9pZCBidWlsZChjb25zdCB2ZWN0b3I8aW50PiYgYSkgewogICAgICAgIG4gPSAoaW50KWEuc2l6ZSgpOwogICAgICAgIGJpdC5hc3NpZ24obiArIDEsIDApOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgICAgICBiaXRbaSArIDFdICs9IGFbaV07CgogICAgICAgICAgICBpbnQgcGFyZW50ID0gaSArIDEgKyAoKGkgKyAxKSAmIC0oaSArIDEpKTsKICAgICAgICAgICAgaWYgKHBhcmVudCA8PSBuKSB7CiAgICAgICAgICAgICAgICBiaXRbcGFyZW50XSArPSBiaXRbaSArIDFdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgYWRkKGludCBpbmRleCwgaW50IHZhbHVlKSB7CiAgICAgICAgZm9yIChpbnQgaSA9IGluZGV4ICsgMTsgaSA8PSBuOyBpICs9IGkgJiAtaSkgewogICAgICAgICAgICBiaXRbaV0gKz0gdmFsdWU7CiAgICAgICAgfQogICAgfQoKICAgIC8vIFThu5VuZyBrw61jaCB0aMaw4bubYyBjw6FjIGJsb2NrIGPDsyBjaOG7iSBz4buRIDwgaW5kZXguCiAgICBpbnQgcHJlZml4QmVmb3JlKGludCBpbmRleCkgY29uc3QgewogICAgICAgIGludCByZXN1bHQgPSAwOwoKICAgICAgICBmb3IgKGludCBpID0gaW5kZXg7IGkgPiAwOyBpIC09IGkgJiAtaSkgewogICAgICAgICAgICByZXN1bHQgKz0gYml0W2ldOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KCiAgICAvLyBUcuG6oyB24buBIGJsb2NrIGNo4bupYSBwaOG6p24gdOG7rSB0aOG7qSBrLCB24bubaSBrIMSRw6FuaCBz4buRIHThu6sgMS4KICAgIGludCBrdGgoaW50IGspIGNvbnN0IHsKICAgICAgICBpbnQgaW5kZXggPSAwOwogICAgICAgIGludCBjdXJyZW50U3VtID0gMDsKCiAgICAgICAgaW50IHN0ZXAgPSAxOwogICAgICAgIHdoaWxlICgoc3RlcCA8PCAxKSA8PSBuKSB7CiAgICAgICAgICAgIHN0ZXAgPDw9IDE7CiAgICAgICAgfQoKICAgICAgICBmb3IgKDsgc3RlcCA+IDA7IHN0ZXAgPj49IDEpIHsKICAgICAgICAgICAgaW50IG5leHRJbmRleCA9IGluZGV4ICsgc3RlcDsKCiAgICAgICAgICAgIGlmIChuZXh0SW5kZXggPD0gbiAmJgogICAgICAgICAgICAgICAgY3VycmVudFN1bSArIGJpdFtuZXh0SW5kZXhdIDwgaykgewogICAgICAgICAgICAgICAgaW5kZXggPSBuZXh0SW5kZXg7CiAgICAgICAgICAgICAgICBjdXJyZW50U3VtICs9IGJpdFtuZXh0SW5kZXhdOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gaW5kZXg7CiAgICB9Cn07CgpzdHJ1Y3QgRHluYW1pY09yZGVyIHsKICAgIHN0YXRpYyBjb25zdGV4cHIgaW50IEJMT0NLX1NJWkUgPSAxMjg7CgogICAgc3RydWN0IEJsb2NrIHsKICAgICAgICB2ZWN0b3I8aW50PiBlbGVtZW50czsKICAgICAgICBpbnQgb3JkZXIgPSAtMTsKICAgIH07CgogICAgaW50IG47CgogICAgdmVjdG9yPEJsb2NrKj4gYmxvY2tzOwogICAgdmVjdG9yPEJsb2NrKj4gb3duZXI7CiAgICB2ZWN0b3I8aW50PiBwb3NpdGlvbkluQmxvY2s7CgogICAgRmVud2ljayBmZW53aWNrOwoKICAgIER5bmFtaWNPcmRlcihjb25zdCB2ZWN0b3I8aW50PiYgc2VxdWVuY2UsIGludCBudW1iZXJPZkVsZW1lbnRzKQogICAgICAgIDogbihudW1iZXJPZkVsZW1lbnRzKSwKICAgICAgICAgIG93bmVyKG4gKyAxKSwKICAgICAgICAgIHBvc2l0aW9uSW5CbG9jayhuICsgMSkgewogICAgICAgIGZvciAoaW50IGxlZnQgPSAwOyBsZWZ0IDwgbjsgbGVmdCArPSBCTE9DS19TSVpFKSB7CiAgICAgICAgICAgIGludCByaWdodCA9IG1pbihuLCBsZWZ0ICsgQkxPQ0tfU0laRSk7CgogICAgICAgICAgICBCbG9jayogYmxvY2sgPSBuZXcgQmxvY2soKTsKICAgICAgICAgICAgYmxvY2stPmVsZW1lbnRzLnJlc2VydmUoMiAqIEJMT0NLX1NJWkUgKyAxKTsKCiAgICAgICAgICAgIGZvciAoaW50IGkgPSBsZWZ0OyBpIDwgcmlnaHQ7ICsraSkgewogICAgICAgICAgICAgICAgaW50IHZhbHVlID0gc2VxdWVuY2VbaV07CgogICAgICAgICAgICAgICAgb3duZXJbdmFsdWVdID0gYmxvY2s7CiAgICAgICAgICAgICAgICBwb3NpdGlvbkluQmxvY2tbdmFsdWVdID0KICAgICAgICAgICAgICAgICAgICAoaW50KWJsb2NrLT5lbGVtZW50cy5zaXplKCk7CgogICAgICAgICAgICAgICAgYmxvY2stPmVsZW1lbnRzLnB1c2hfYmFjayh2YWx1ZSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGJsb2NrLT5vcmRlciA9IChpbnQpYmxvY2tzLnNpemUoKTsKICAgICAgICAgICAgYmxvY2tzLnB1c2hfYmFjayhibG9jayk7CiAgICAgICAgfQoKICAgICAgICByZWJ1aWxkRmVud2ljaygpOwogICAgfQoKICAgIH5EeW5hbWljT3JkZXIoKSB7CiAgICAgICAgZm9yIChCbG9jayogYmxvY2sgOiBibG9ja3MpIHsKICAgICAgICAgICAgZGVsZXRlIGJsb2NrOwogICAgICAgIH0KICAgIH0KCiAgICB2b2lkIHJlYnVpbGRGZW53aWNrKCkgewogICAgICAgIHZlY3RvcjxpbnQ+IHNpemVzKGJsb2Nrcy5zaXplKCkpOwoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpYmxvY2tzLnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgIGJsb2Nrc1tpXS0+b3JkZXIgPSBpOwogICAgICAgICAgICBzaXplc1tpXSA9IChpbnQpYmxvY2tzW2ldLT5lbGVtZW50cy5zaXplKCk7CiAgICAgICAgfQoKICAgICAgICBmZW53aWNrLmJ1aWxkKHNpemVzKTsKICAgIH0KCiAgICAvLyB0cnVlIGtoaSBo4bqhbmcgYW4gdG/DoG4gY+G7p2EgeCBuaOG7jyBoxqFuIGjhuqFuZyBj4bunYSB5LgogICAgYm9vbCBiZWZvcmUoaW50IHgsIGludCB5KSBjb25zdCB7CiAgICAgICAgaWYgKG93bmVyW3hdID09IG93bmVyW3ldKSB7CiAgICAgICAgICAgIHJldHVybiBwb3NpdGlvbkluQmxvY2tbeF0gPCBwb3NpdGlvbkluQmxvY2tbeV07CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gb3duZXJbeF0tPm9yZGVyIDwgb3duZXJbeV0tPm9yZGVyOwogICAgfQoKICAgIC8vIFBo4bqnbiB04butIGPDsyBo4bqhbmcgbOG7m24gaMahbiwgdOG7qWMga8OpbSBhbiB0b8OgbiBoxqFuLgogICAgaW50IGxhdGVyKGludCB4LCBpbnQgeSkgY29uc3QgewogICAgICAgIGlmICh4ID09IC0xKSB7CiAgICAgICAgICAgIHJldHVybiB5OwogICAgICAgIH0KCiAgICAgICAgaWYgKHkgPT0gLTEpIHsKICAgICAgICAgICAgcmV0dXJuIHg7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gYmVmb3JlKHgsIHkpID8geSA6IHg7CiAgICB9CgogICAgYm9vbCBhdExlYXN0KGludCB4LCBpbnQgdGhyZXNob2xkKSBjb25zdCB7CiAgICAgICAgcmV0dXJuICFiZWZvcmUoeCwgdGhyZXNob2xkKTsKICAgIH0KCiAgICB2b2lkIGVyYXNlRnJvbUJsb2NrKEJsb2NrKiBibG9jaywgaW50IGluZGV4KSB7CiAgICAgICAgYmxvY2stPmVsZW1lbnRzLmVyYXNlKGJsb2NrLT5lbGVtZW50cy5iZWdpbigpICsgaW5kZXgpOwoKICAgICAgICBmb3IgKGludCBpID0gaW5kZXg7CiAgICAgICAgICAgICBpIDwgKGludClibG9jay0+ZWxlbWVudHMuc2l6ZSgpOwogICAgICAgICAgICAgKytpKSB7CiAgICAgICAgICAgIHBvc2l0aW9uSW5CbG9ja1tibG9jay0+ZWxlbWVudHNbaV1dID0gaTsKICAgICAgICB9CiAgICB9CgogICAgdm9pZCBpbnNlcnRJbnRvQmxvY2soQmxvY2sqIGJsb2NrLCBpbnQgaW5kZXgsIGludCB2YWx1ZSkgewogICAgICAgIGJsb2NrLT5lbGVtZW50cy5pbnNlcnQoCiAgICAgICAgICAgIGJsb2NrLT5lbGVtZW50cy5iZWdpbigpICsgaW5kZXgsCiAgICAgICAgICAgIHZhbHVlCiAgICAgICAgKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IGluZGV4OwogICAgICAgICAgICAgaSA8IChpbnQpYmxvY2stPmVsZW1lbnRzLnNpemUoKTsKICAgICAgICAgICAgICsraSkgewogICAgICAgICAgICBpbnQgZWxlbWVudCA9IGJsb2NrLT5lbGVtZW50c1tpXTsKCiAgICAgICAgICAgIG93bmVyW2VsZW1lbnRdID0gYmxvY2s7CiAgICAgICAgICAgIHBvc2l0aW9uSW5CbG9ja1tlbGVtZW50XSA9IGk7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgc3BsaXRJZk5lZWRlZChCbG9jayogYmxvY2spIHsKICAgICAgICBpZiAoKGludClibG9jay0+ZWxlbWVudHMuc2l6ZSgpIDw9CiAgICAgICAgICAgIDIgKiBCTE9DS19TSVpFKSB7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIGludCBibG9ja0luZGV4ID0gYmxvY2stPm9yZGVyOwogICAgICAgIGludCBtaWRkbGUgPSAoaW50KWJsb2NrLT5lbGVtZW50cy5zaXplKCkgLyAyOwoKICAgICAgICBCbG9jayogbmV3QmxvY2sgPSBuZXcgQmxvY2soKTsKICAgICAgICBuZXdCbG9jay0+ZWxlbWVudHMucmVzZXJ2ZSgyICogQkxPQ0tfU0laRSArIDEpOwoKICAgICAgICBuZXdCbG9jay0+ZWxlbWVudHMuYXNzaWduKAogICAgICAgICAgICBibG9jay0+ZWxlbWVudHMuYmVnaW4oKSArIG1pZGRsZSwKICAgICAgICAgICAgYmxvY2stPmVsZW1lbnRzLmVuZCgpCiAgICAgICAgKTsKCiAgICAgICAgYmxvY2stPmVsZW1lbnRzLmVyYXNlKAogICAgICAgICAgICBibG9jay0+ZWxlbWVudHMuYmVnaW4oKSArIG1pZGRsZSwKICAgICAgICAgICAgYmxvY2stPmVsZW1lbnRzLmVuZCgpCiAgICAgICAgKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7CiAgICAgICAgICAgICBpIDwgKGludCluZXdCbG9jay0+ZWxlbWVudHMuc2l6ZSgpOwogICAgICAgICAgICAgKytpKSB7CiAgICAgICAgICAgIGludCBlbGVtZW50ID0gbmV3QmxvY2stPmVsZW1lbnRzW2ldOwoKICAgICAgICAgICAgb3duZXJbZWxlbWVudF0gPSBuZXdCbG9jazsKICAgICAgICAgICAgcG9zaXRpb25JbkJsb2NrW2VsZW1lbnRdID0gaTsKICAgICAgICB9CgogICAgICAgIGJsb2Nrcy5pbnNlcnQoCiAgICAgICAgICAgIGJsb2Nrcy5iZWdpbigpICsgYmxvY2tJbmRleCArIDEsCiAgICAgICAgICAgIG5ld0Jsb2NrCiAgICAgICAgKTsKCiAgICAgICAgcmVidWlsZEZlbndpY2soKTsKICAgIH0KCiAgICAvLyDEkMawYSB4IHThu5tpIGjhuqFuZyByYW5rLCByYW5rIMSRw6FuaCBz4buRIHThu6sgMS4KICAgIHZvaWQgbW92ZVRvUmFuayhpbnQgeCwgaW50IHJhbmspIHsKICAgICAgICBCbG9jayogc291cmNlQmxvY2sgPSBvd25lclt4XTsKICAgICAgICBpbnQgc291cmNlQmxvY2tJbmRleCA9IHNvdXJjZUJsb2NrLT5vcmRlcjsKICAgICAgICBpbnQgc291cmNlUG9zaXRpb24gPSBwb3NpdGlvbkluQmxvY2tbeF07CgogICAgICAgIGVyYXNlRnJvbUJsb2NrKHNvdXJjZUJsb2NrLCBzb3VyY2VQb3NpdGlvbik7CiAgICAgICAgZmVud2ljay5hZGQoc291cmNlQmxvY2tJbmRleCwgLTEpOwoKICAgICAgICBpbnQgdGFyZ2V0QmxvY2tJbmRleCA9IGZlbndpY2sua3RoKHJhbmspOwogICAgICAgIGludCBlbGVtZW50c0JlZm9yZSA9CiAgICAgICAgICAgIGZlbndpY2sucHJlZml4QmVmb3JlKHRhcmdldEJsb2NrSW5kZXgpOwoKICAgICAgICBpbnQgdGFyZ2V0UG9zaXRpb24gPQogICAgICAgICAgICByYW5rIC0gZWxlbWVudHNCZWZvcmUgLSAxOwoKICAgICAgICBCbG9jayogdGFyZ2V0QmxvY2sgPSBibG9ja3NbdGFyZ2V0QmxvY2tJbmRleF07CgogICAgICAgIGluc2VydEludG9CbG9jaygKICAgICAgICAgICAgdGFyZ2V0QmxvY2ssCiAgICAgICAgICAgIHRhcmdldFBvc2l0aW9uLAogICAgICAgICAgICB4CiAgICAgICAgKTsKCiAgICAgICAgZmVud2ljay5hZGQodGFyZ2V0QmxvY2tJbmRleCwgMSk7CgogICAgICAgIHNwbGl0SWZOZWVkZWQodGFyZ2V0QmxvY2spOwogICAgfQp9OwoKc3RydWN0IFNlZ21lbnRUcmVlIHsKICAgIGludCBuOwogICAgaW50IHNpemU7CgogICAgdmVjdG9yPGludD4gdHJlZTsKICAgIER5bmFtaWNPcmRlciogb3JkZXI7CgogICAgU2VnbWVudFRyZWUoaW50IG51bWJlck9mUG9zaXRpb25zLCBEeW5hbWljT3JkZXIqIG9yZGVyU3RydWN0dXJlKQogICAgICAgIDogbihudW1iZXJPZlBvc2l0aW9ucyksIG9yZGVyKG9yZGVyU3RydWN0dXJlKSB7CiAgICAgICAgc2l6ZSA9IDE7CgogICAgICAgIHdoaWxlIChzaXplIDwgbikgewogICAgICAgICAgICBzaXplIDw8PSAxOwogICAgICAgIH0KCiAgICAgICAgdHJlZS5hc3NpZ24oc2l6ZSA8PCAxLCAtMSk7CgogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgICAgICAgICB0cmVlW3NpemUgKyBpIC0gMV0gPSBpOwogICAgICAgIH0KCiAgICAgICAgZm9yIChpbnQgbm9kZSA9IHNpemUgLSAxOyBub2RlID49IDE7IC0tbm9kZSkgewogICAgICAgICAgICB0cmVlW25vZGVdID0gb3JkZXItPmxhdGVyKAogICAgICAgICAgICAgICAgdHJlZVtub2RlIDw8IDFdLAogICAgICAgICAgICAgICAgdHJlZVtub2RlIDw8IDEgfCAxXQogICAgICAgICAgICApOwogICAgICAgIH0KICAgIH0KCiAgICB2b2lkIHJlZnJlc2goaW50IHBvc2l0aW9uKSB7CiAgICAgICAgaW50IG5vZGUgPSBzaXplICsgcG9zaXRpb24gLSAxOwoKICAgICAgICBmb3IgKG5vZGUgPj49IDE7IG5vZGUgPiAwOyBub2RlID4+PSAxKSB7CiAgICAgICAgICAgIHRyZWVbbm9kZV0gPSBvcmRlci0+bGF0ZXIoCiAgICAgICAgICAgICAgICB0cmVlW25vZGUgPDwgMV0sCiAgICAgICAgICAgICAgICB0cmVlW25vZGUgPDwgMSB8IDFdCiAgICAgICAgICAgICk7CiAgICAgICAgfQogICAgfQoKICAgIGludCByYW5nZU1heGltdW0oaW50IGxlZnQsIGludCByaWdodCkgY29uc3QgewogICAgICAgIGludCBsZWZ0UmVzdWx0ID0gLTE7CiAgICAgICAgaW50IHJpZ2h0UmVzdWx0ID0gLTE7CgogICAgICAgIGludCBsID0gc2l6ZSArIGxlZnQgLSAxOwogICAgICAgIGludCByID0gc2l6ZSArIHJpZ2h0IC0gMTsKCiAgICAgICAgd2hpbGUgKGwgPD0gcikgewogICAgICAgICAgICBpZiAobCAmIDEpIHsKICAgICAgICAgICAgICAgIGxlZnRSZXN1bHQgPQogICAgICAgICAgICAgICAgICAgIG9yZGVyLT5sYXRlcihsZWZ0UmVzdWx0LCB0cmVlW2xdKTsKICAgICAgICAgICAgICAgICsrbDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKCEociAmIDEpKSB7CiAgICAgICAgICAgICAgICByaWdodFJlc3VsdCA9CiAgICAgICAgICAgICAgICAgICAgb3JkZXItPmxhdGVyKHRyZWVbcl0sIHJpZ2h0UmVzdWx0KTsKICAgICAgICAgICAgICAgIC0tcjsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgbCA+Pj0gMTsKICAgICAgICAgICAgciA+Pj0gMTsKICAgICAgICB9CgogICAgICAgIHJldHVybiBvcmRlci0+bGF0ZXIobGVmdFJlc3VsdCwgcmlnaHRSZXN1bHQpOwogICAgfQoKICAgIGludCBmaW5kTGFzdFJlY3Vyc2l2ZSgKICAgICAgICBpbnQgbm9kZSwKICAgICAgICBpbnQgbm9kZUxlZnQsCiAgICAgICAgaW50IG5vZGVSaWdodCwKICAgICAgICBpbnQgcXVlcnlMZWZ0LAogICAgICAgIGludCBxdWVyeVJpZ2h0LAogICAgICAgIGludCB0aHJlc2hvbGQKICAgICkgY29uc3QgewogICAgICAgIGlmIChub2RlUmlnaHQgPCBxdWVyeUxlZnQgfHwKICAgICAgICAgICAgcXVlcnlSaWdodCA8IG5vZGVMZWZ0IHx8CiAgICAgICAgICAgIHRyZWVbbm9kZV0gPT0gLTEgfHwKICAgICAgICAgICAgIW9yZGVyLT5hdExlYXN0KHRyZWVbbm9kZV0sIHRocmVzaG9sZCkpIHsKICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgIH0KCiAgICAgICAgaWYgKG5vZGVMZWZ0ID09IG5vZGVSaWdodCkgewogICAgICAgICAgICByZXR1cm4gbm9kZUxlZnQ7CiAgICAgICAgfQoKICAgICAgICBpbnQgbWlkZGxlID0gKG5vZGVMZWZ0ICsgbm9kZVJpZ2h0KSA+PiAxOwoKICAgICAgICBpbnQgcmVzdWx0ID0gZmluZExhc3RSZWN1cnNpdmUoCiAgICAgICAgICAgIG5vZGUgPDwgMSB8IDEsCiAgICAgICAgICAgIG1pZGRsZSArIDEsCiAgICAgICAgICAgIG5vZGVSaWdodCwKICAgICAgICAgICAgcXVlcnlMZWZ0LAogICAgICAgICAgICBxdWVyeVJpZ2h0LAogICAgICAgICAgICB0aHJlc2hvbGQKICAgICAgICApOwoKICAgICAgICBpZiAocmVzdWx0ICE9IC0xKSB7CiAgICAgICAgICAgIHJldHVybiByZXN1bHQ7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gZmluZExhc3RSZWN1cnNpdmUoCiAgICAgICAgICAgIG5vZGUgPDwgMSwKICAgICAgICAgICAgbm9kZUxlZnQsCiAgICAgICAgICAgIG1pZGRsZSwKICAgICAgICAgICAgcXVlcnlMZWZ0LAogICAgICAgICAgICBxdWVyeVJpZ2h0LAogICAgICAgICAgICB0aHJlc2hvbGQKICAgICAgICApOwogICAgfQoKICAgIGludCBmaW5kRmlyc3RSZWN1cnNpdmUoCiAgICAgICAgaW50IG5vZGUsCiAgICAgICAgaW50IG5vZGVMZWZ0LAogICAgICAgIGludCBub2RlUmlnaHQsCiAgICAgICAgaW50IHF1ZXJ5TGVmdCwKICAgICAgICBpbnQgcXVlcnlSaWdodCwKICAgICAgICBpbnQgdGhyZXNob2xkCiAgICApIGNvbnN0IHsKICAgICAgICBpZiAobm9kZVJpZ2h0IDwgcXVlcnlMZWZ0IHx8CiAgICAgICAgICAgIHF1ZXJ5UmlnaHQgPCBub2RlTGVmdCB8fAogICAgICAgICAgICB0cmVlW25vZGVdID09IC0xIHx8CiAgICAgICAgICAgICFvcmRlci0+YXRMZWFzdCh0cmVlW25vZGVdLCB0aHJlc2hvbGQpKSB7CiAgICAgICAgICAgIHJldHVybiAtMTsKICAgICAgICB9CgogICAgICAgIGlmIChub2RlTGVmdCA9PSBub2RlUmlnaHQpIHsKICAgICAgICAgICAgcmV0dXJuIG5vZGVMZWZ0OwogICAgICAgIH0KCiAgICAgICAgaW50IG1pZGRsZSA9IChub2RlTGVmdCArIG5vZGVSaWdodCkgPj4gMTsKCiAgICAgICAgaW50IHJlc3VsdCA9IGZpbmRGaXJzdFJlY3Vyc2l2ZSgKICAgICAgICAgICAgbm9kZSA8PCAxLAogICAgICAgICAgICBub2RlTGVmdCwKICAgICAgICAgICAgbWlkZGxlLAogICAgICAgICAgICBxdWVyeUxlZnQsCiAgICAgICAgICAgIHF1ZXJ5UmlnaHQsCiAgICAgICAgICAgIHRocmVzaG9sZAogICAgICAgICk7CgogICAgICAgIGlmIChyZXN1bHQgIT0gLTEpIHsKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgICAgICB9CgogICAgICAgIHJldHVybiBmaW5kRmlyc3RSZWN1cnNpdmUoCiAgICAgICAgICAgIG5vZGUgPDwgMSB8IDEsCiAgICAgICAgICAgIG1pZGRsZSArIDEsCiAgICAgICAgICAgIG5vZGVSaWdodCwKICAgICAgICAgICAgcXVlcnlMZWZ0LAogICAgICAgICAgICBxdWVyeVJpZ2h0LAogICAgICAgICAgICB0aHJlc2hvbGQKICAgICAgICApOwogICAgfQoKICAgIGludCBmaW5kTGFzdCgKICAgICAgICBpbnQgbGVmdCwKICAgICAgICBpbnQgcmlnaHQsCiAgICAgICAgaW50IHRocmVzaG9sZAogICAgKSBjb25zdCB7CiAgICAgICAgaWYgKGxlZnQgPiByaWdodCkgewogICAgICAgICAgICByZXR1cm4gLTE7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gZmluZExhc3RSZWN1cnNpdmUoCiAgICAgICAgICAgIDEsCiAgICAgICAgICAgIDEsCiAgICAgICAgICAgIHNpemUsCiAgICAgICAgICAgIGxlZnQsCiAgICAgICAgICAgIHJpZ2h0LAogICAgICAgICAgICB0aHJlc2hvbGQKICAgICAgICApOwogICAgfQoKICAgIGludCBmaW5kRmlyc3QoCiAgICAgICAgaW50IGxlZnQsCiAgICAgICAgaW50IHJpZ2h0LAogICAgICAgIGludCB0aHJlc2hvbGQKICAgICkgY29uc3QgewogICAgICAgIGlmIChsZWZ0ID4gcmlnaHQpIHsKICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGZpbmRGaXJzdFJlY3Vyc2l2ZSgKICAgICAgICAgICAgMSwKICAgICAgICAgICAgMSwKICAgICAgICAgICAgc2l6ZSwKICAgICAgICAgICAgbGVmdCwKICAgICAgICAgICAgcmlnaHQsCiAgICAgICAgICAgIHRocmVzaG9sZAogICAgICAgICk7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CgogICAgZnJlb3BlbigidmkuSU5QIiAsICJyIiAsIHN0ZGluKTsKICAgIGZyZW9wZW4oInZpLk9VVCIgLCAidyIgLCBzdGRvdXQpOwogICAgCiAgICBpbnQgc3VidGFzazsKICAgIGNpbiA+PiBzdWJ0YXNrOwoKICAgIGludCBuLCBxLCBmYXZvdXJpdGU7CiAgICBjaW4gPj4gbiA+PiBxID4+IGZhdm91cml0ZTsKCiAgICB2ZWN0b3I8aW50PiBzYWZldHkobiArIDEpOwogICAgdmVjdG9yPGludD4gcG9zaXRpb25BdFJhbmsobik7CgogICAgZm9yIChpbnQgcG9zaXRpb24gPSAxOyBwb3NpdGlvbiA8PSBuOyArK3Bvc2l0aW9uKSB7CiAgICAgICAgY2luID4+IHNhZmV0eVtwb3NpdGlvbl07CiAgICAgICAgcG9zaXRpb25BdFJhbmtbc2FmZXR5W3Bvc2l0aW9uXSAtIDFdID0gcG9zaXRpb247CiAgICB9CgogICAgRHluYW1pY09yZGVyIG9yZGVyKHBvc2l0aW9uQXRSYW5rLCBuKTsKICAgIFNlZ21lbnRUcmVlIHNlZ21lbnRUcmVlKG4sICZvcmRlcik7CgogICAgd2hpbGUgKHEtLSkgewogICAgICAgIGNoYXIgdHlwZTsKICAgICAgICBjaW4gPj4gdHlwZTsKCiAgICAgICAgaWYgKHR5cGUgPT0gJ1UnKSB7CiAgICAgICAgICAgIGludCBwb3NpdGlvbiwgbmV3UmFuazsKICAgICAgICAgICAgY2luID4+IHBvc2l0aW9uID4+IG5ld1Jhbms7CgogICAgICAgICAgICAvKgogICAgICAgICAgICBTYXUgY+G6rXAgbmjhuq10LCBxdWFuIGjhu4cgdGjhu6kgdOG7sSBnaeG7r2EgbeG7jWkgY+G6t3AgduG7iyB0csOtCiAgICAgICAgICAgIGtow7RuZyBjaOG7qWEgcG9zaXRpb24gduG6q24gZ2nhu68gbmd1ecOqbi4gVsOsIHbhuq15IGNo4buJIGPhuqduCiAgICAgICAgICAgIGPhuq1wIG5o4bqtdCDEkcaw4budbmcgxJFpIGPhu6dhIHBvc2l0aW9uIHRyw6puIHNlZ21lbnQgdHJlZS4KICAgICAgICAgICAgKi8KICAgICAgICAgICAgb3JkZXIubW92ZVRvUmFuayhwb3NpdGlvbiwgbmV3UmFuayk7CiAgICAgICAgICAgIHNlZ21lbnRUcmVlLnJlZnJlc2gocG9zaXRpb24pOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGludCBwb3NpdGlvbjsKICAgICAgICAgICAgY2luID4+IHBvc2l0aW9uOwoKICAgICAgICAgICAgaWYgKHBvc2l0aW9uID09IGZhdm91cml0ZSkgewogICAgICAgICAgICAgICAgY291dCA8PCAxIDw8ICdcbic7CiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKHBvc2l0aW9uID4gZmF2b3VyaXRlKSB7CiAgICAgICAgICAgICAgICAvKgogICAgICAgICAgICAgICAgSOG6oW5nIGzhu5tuIG5o4bqldCB0csOqbiDEkW/huqFuIHThu6sgZmF2b3VyaXRlICsgMQogICAgICAgICAgICAgICAgdOG7m2kgcG9zaXRpb24uCiAgICAgICAgICAgICAgICAqLwogICAgICAgICAgICAgICAgaW50IHRocmVzaG9sZCA9IHNlZ21lbnRUcmVlLnJhbmdlTWF4aW11bSgKICAgICAgICAgICAgICAgICAgICBmYXZvdXJpdGUgKyAxLAogICAgICAgICAgICAgICAgICAgIHBvc2l0aW9uCiAgICAgICAgICAgICAgICApOwoKICAgICAgICAgICAgICAgIC8qCiAgICAgICAgICAgICAgICBW4buLIHRyw60gZ+G6p24gZmF2b3VyaXRlIG5o4bqldCDhu58gcGjDrWEgdHLDoWkgY8OzCiAgICAgICAgICAgICAgICBo4bqhbmcga2jDtG5nIG5o4buPIGjGoW4gdGhyZXNob2xkLgogICAgICAgICAgICAgICAgKi8KICAgICAgICAgICAgICAgIGludCBibG9ja2VyID0gc2VnbWVudFRyZWUuZmluZExhc3QoCiAgICAgICAgICAgICAgICAgICAgMSwKICAgICAgICAgICAgICAgICAgICBmYXZvdXJpdGUgLSAxLAogICAgICAgICAgICAgICAgICAgIHRocmVzaG9sZAogICAgICAgICAgICAgICAgKTsKCiAgICAgICAgICAgICAgICBpbnQgb3Bwb3NpdGVTZWF0c0JlZm9yZTsKCiAgICAgICAgICAgICAgICBpZiAoYmxvY2tlciA9PSAtMSkgewogICAgICAgICAgICAgICAgICAgIG9wcG9zaXRlU2VhdHNCZWZvcmUgPSBmYXZvdXJpdGUgLSAxOwogICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICBvcHBvc2l0ZVNlYXRzQmVmb3JlID0KICAgICAgICAgICAgICAgICAgICAgICAgZmF2b3VyaXRlIC0gYmxvY2tlciAtIDE7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgY291dCA8PCBwb3NpdGlvbiAtIGZhdm91cml0ZSArIDEKICAgICAgICAgICAgICAgICAgICAgICAgICAgICArIG9wcG9zaXRlU2VhdHNCZWZvcmUKICAgICAgICAgICAgICAgICAgICAgPDwgJ1xuJzsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGludCB0aHJlc2hvbGQgPSBzZWdtZW50VHJlZS5yYW5nZU1heGltdW0oCiAgICAgICAgICAgICAgICAgICAgcG9zaXRpb24sCiAgICAgICAgICAgICAgICAgICAgZmF2b3VyaXRlIC0gMQogICAgICAgICAgICAgICAgKTsKCiAgICAgICAgICAgICAgICBpbnQgYmxvY2tlciA9IHNlZ21lbnRUcmVlLmZpbmRGaXJzdCgKICAgICAgICAgICAgICAgICAgICBmYXZvdXJpdGUgKyAxLAogICAgICAgICAgICAgICAgICAgIG4sCiAgICAgICAgICAgICAgICAgICAgdGhyZXNob2xkCiAgICAgICAgICAgICAgICApOwoKICAgICAgICAgICAgICAgIGludCBvcHBvc2l0ZVNlYXRzQmVmb3JlOwoKICAgICAgICAgICAgICAgIGlmIChibG9ja2VyID09IC0xKSB7CiAgICAgICAgICAgICAgICAgICAgb3Bwb3NpdGVTZWF0c0JlZm9yZSA9IG4gLSBmYXZvdXJpdGU7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIG9wcG9zaXRlU2VhdHNCZWZvcmUgPQogICAgICAgICAgICAgICAgICAgICAgICBibG9ja2VyIC0gZmF2b3VyaXRlIC0gMTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBjb3V0IDw8IGZhdm91cml0ZSAtIHBvc2l0aW9uICsgMQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICsgb3Bwb3NpdGVTZWF0c0JlZm9yZQogICAgICAgICAgICAgICAgICAgICA8PCAnXG4nOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiAwOwp9Cg==