c solution...

include

include

include

include

include

// Treap without rotating operations struct Node { struct Node *left, *right; int data; int pri; // priority of this Treap Node int size; // Order Statistic Tree, used for relocating elements }; typedef struct Node Node;

inline Node* new_Node(int v) { Node* node = (Node*) malloc(sizeof(Node)); node->left = node->right = NULL; node->data = v; node->pri = rand(); node->size = 1; return node; }

inline int Node_get_size(Node* node) { if (node) return node->size; return 0; }

// Merge lt & rt, lt must be on the left-side of rt Node* merge(Node* lt, Node* rt) { if (lt == NULL && rt == NULL) return NULL;

if (lt == NULL)
    return rt;
if (rt == NULL)
    return lt;

// lt is on the top of rt
if (lt->pri < rt->pri) {
    lt->right = merge(lt->right, rt);
    lt->size = Node_get_size(lt->left) + Node_get_size(lt->right) + 1;
    return lt;
}
// rt is on the top of lt
else {
    rt->left = merge(lt, rt->left);
    rt->size = Node_get_size(rt->left) + Node_get_size(rt->right) + 1;
    return rt;
}

}

// split k nodes to the returned tree from *ref_tree // *ref_tree will be modified during splitting // as a result, splitted_tree will have k nodes // and ref_tree will have (n-k) nodes Node split(Node** ref_tree, int k) { Node* tree = *ref_tree;

if (tree == NULL)
    return NULL;

Node* splited_tree;

if (Node_get_size(tree->left) >= k) {
    splited_tree = split(&tree->left, k);
}
else {
    k -= (Node_get_size(tree->left) + 1);

    splited_tree = tree;
    *ref_tree = splited_tree->right;

    splited_tree->right = split(ref_tree, k);

    tree = *ref_tree;
}

if (splited_tree)
    splited_tree->size = Node_get_size(splited_tree->left) + Node_get_size(splited_tree->right) + 1;
if (tree)
    tree->size = Node_get_size(tree->left) + Node_get_size(tree->right) + 1;

return splited_tree;

}

// print the inorder traversal of the Treap void print_inorder(Node* root) { if (!root) return; print_inorder(root->left); printf("%d ", root->data); print_inorder(root->right); }

int main() { srand(clock());

int N, M;

while (scanf("%d %d", &N, &M) != EOF) {

    Node* root = NULL;
    for (int i = 0; i < N; ++i) {
        int v;
        scanf("%d", &v);
        Node* node = new_Node(v);
        root = merge(root, node);
    }

    for (int i = 0; i < M; ++i) {
        int type, l, r;
        scanf("%d %d %d", &type, &l, &r);

        Node* lt = split(&root, l-1);
        Node* mt = split(&root, r-l+1);
        Node* rt = root;

        if (type == 1) {
            root = merge(merge(mt, lt), rt);
        }
        else{
            root = merge(lt, merge(rt, mt));
        }
    }

    Node* lt = split(&root, 1);
    Node* mt = split(&root, Node_get_size(root)-1);
    Node* rt = root;

    #define ABS(x) ((x) > 0 ? (x) : -(x))
    printf("%d\n", ABS(lt->data - rt->data));
    #undef ABS

    root = merge(merge(lt, mt), rt);

    print_inorder(root);
}

return 0;

}