2789

#include <iostream>
#include <fstream>
#include <ctime>
#include <random>
#include <tuple>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

class TreapNode
{
public:
    TreapNode(int val) :
        val(val),
        size(1),
        sum(val),
        prior((rand() << 16) | rand()),
        l(nullptr),
        r(nullptr){}

    int get_val() { return val; }
    int get_size() { return size; }
    int get_sum() { return (this == nullptr ? 0 : sum); }
    int get_prior() { return prior; }
    TreapNode* get_l() { relax(); return l; }
    TreapNode* get_r() { relax(); return r; }
    void set_l(TreapNode* l) { this->l = l; relax(); }
    void set_r(TreapNode* r) { this->r = r; relax(); }

private:
    int val;
    int size;
    int sum;
    int prior;
    TreapNode* l;
    TreapNode* r;
    void relax();
};

void TreapNode::relax() {
    int size_l = (l == nullptr ? 0 : l->get_size());
    int size_r = (r == nullptr ? 0 : r->get_size());
    size = size_l + 1 + size_r;

    int sum_l = (l == nullptr ? 0 : l->get_sum());
    int sum_r = (r == nullptr ? 0 : r->get_sum());
    sum = sum_l + val + sum_r;
}

class Treap {
public:
    Treap() : even(nullptr), odd(nullptr) {}
    void Add_even(int val) { even = merge(even, new TreapNode(val)); }
    void Add_odd(int val) { odd = merge(odd, new TreapNode(val)); }
    void Swap(int l, int r);
    int Sum(int l, int r);
private:
    TreapNode* even;
    TreapNode* odd;
    TreapNode* merge(TreapNode* t1, TreapNode* t2);
    TreapNode* merge(TreapNode* t1, TreapNode* t2, TreapNode* t3);
    tuple<TreapNode*, TreapNode*> split(TreapNode* t, int x);
    tuple<TreapNode*, TreapNode*, TreapNode*> split(TreapNode* t, int l, int r);
};

TreapNode* Treap::merge(TreapNode* t1, TreapNode* t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;
    if (t1->get_prior() > t2->get_prior()) {
        t1->set_r(merge(t1->get_r(), t2));
        return t1;
    }
    else {
        t2->set_l(merge(t1, t2->get_l()));
        return t2;
    }
}
TreapNode* Treap::merge(TreapNode* t1, TreapNode* t2, TreapNode* t3) {
    return merge(t1, merge(t2, t3));
}

tuple<TreapNode*, TreapNode*> Treap::split(TreapNode* t, int x) {
    if (t == nullptr) return make_tuple(nullptr, nullptr);
    int size_l = (t->get_l() == nullptr ? 0 : t->get_l()->get_size());
    if (x <= size_l) {
        auto sp = split(t->get_l(), x);
        t->set_l(get<1>(sp));
        return make_tuple(get<0>(sp), t);
    }
    else {
        auto sp = split(t->get_r(), x - size_l - 1);
        t->set_r(get<0>(sp));
        return make_tuple(t, get<1>(sp));
    }
}
tuple<TreapNode*, TreapNode*, TreapNode*> Treap::split(TreapNode* t, int l, int r) {
    auto sp1 = split(t, r + 1);
    auto sp2 = split(get<0>(sp1), l);
    return make_tuple(get<0>(sp2), get<1>(sp2), get<1>(sp1));
}

int Treap::Sum(int l, int r) {
    if (l > r) return 0;
    int l1 = (l + 1) / 2, r1 = r / 2;
    int l2 = l / 2, r2 = (r + 1) / 2 - 1;
    auto sp_even = split(even, l1, r1);
    auto sp_odd = split(odd, l2, r2);
    int res = get<1>(sp_even)->get_sum() + get<1>(sp_odd)->get_sum();
    merge(get<0>(sp_even), get<1>(sp_even), get<2>(sp_even));
    merge(get<0>(sp_odd), get<1>(sp_odd), get<2>(sp_odd));
    return res;
}

void Treap::Swap(int l, int r) {
    int l1 = (l + 1) / 2, r1 = r / 2;
    int l2 = l / 2, r2 = (r + 1) / 2 - 1;
    auto sp_even = split(even, l1, r1);
    auto sp_odd = split(odd, l2, r2);
    even = merge(get<0>(sp_even), get<1>(sp_odd), get<2>(sp_even));
    odd = merge(get<0>(sp_odd), get<1>(sp_even), get<2>(sp_odd));
}

int main() {
    srand(time(NULL));

    int n, m;
    fin >> n >> m;
    int count = 1;
    while (n + m) {
        fout << "Swapper " << count << ":" << endl;
        Treap tr;
        for (int i = 0; i < n; i++) {
            int a; fin >> a;
            if (i % 2 == 0) tr.Add_even(a);
            else tr.Add_odd(a);
        }
        for (int i = 0; i < m; i++) {
            int a, l, r; fin >> a >> l >> r;
            l--, r--;
            if (a == 1) tr.Swap(l, r);
            else fout << tr.Sum(l, r) << endl;
        }
        fout << endl;
        count++;
        fin >> n >> m;
    }

    fin.close();
    fout.close();
    return 0;
}