#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 4001;
const int MAX_BIT = 11;

class SegmentTree {
  public:
    class Node {
      public:
        Node() {
            sum = 0;
            for (int i = 0; i < 2; ++i)
                left[i] = right[i] = total[i] = 0;
        }

        Node(const int value):
          Node() {
            sum = value;
            left[value] = right[value] = total[value] = 1;
        }

        int EvenSubsequenceCount() const {
            return total[0];
        }

        int OddSubsequenceCount() const {
            return total[1];
        }

        static Node Merge(const Node &left, const Node &right) {
            Node result = Node();
            result.sum = (left.sum + right.sum) & 1;
            for (int i = 0; i < 2; ++i) {
                result.left[i] = left.left[i] + right.left[i ^ left.sum];
                result.right[i] = right.right[i] + left.right[i ^ right.sum];
                result.total[i] = left.total[i] + right.total[i];
                for (int j = 0; j < 2; ++j)
                    result.total[i] += left.right[j] * right.left[i ^ j];
            }
            return result;
        }

      private:
        int sum, left[2], right[2], total[2];
    };

    SegmentTree():
      size(1),
      tree(vector<Node>()) {}

    SegmentTree(const vector<int> &values):
      SegmentTree() {
        for (; size < int(values.size()); size *= 2);
        tree = vector<Node>(2 * size);
        for (int x = 0; x < int(values.size()); ++x)
            tree[size + x] = Node(values[x]);
        for (int x = size - 1; x > 0; --x)
            tree[x] = Node::Merge(tree[2 * x], tree[2 * x + 1]);
    }

    void Update(int where, const int value) {
        tree[where += size] = Node(value);
        for (where /= 2; where > 0; where /= 2)
            tree[where] = Node::Merge(tree[2 * where], tree[2 * where + 1]);
    }

    int Query(const int from, const int to) const {
        return Query(1, 0, size - 1, from, to).OddSubsequenceCount();
    }

  private:
    int size;
    vector<Node> tree;

    Node Query(const int node, const int left, const int right, const int from, const int to) const {
        if (from <= left && right <= to)
            return tree[node];
        int middle = (left + right) / 2;
        Node answer = Node();
        if (from <= middle)
            answer = Node::Merge(answer, Query(2 * node, left, middle, from, to));
        if (middle < to)
            answer = Node::Merge(answer, Query(2 * node + 1, middle + 1, right, from, to));
        return answer;
    }
};

inline int GetBit(const int mask, const int bit) {
    return (mask >> bit) & 1;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> values = vector<int>(n);
    for (int i = 0; i < n; ++i)
        cin >> values[i];
    SegmentTree trees[MAX_BIT];
    for (int bit = 0; bit < MAX_BIT; ++bit) {
        vector<int> bitValues = vector<int>(n);
        for (int i = 0; i < n; ++i)
            bitValues[i] = GetBit(values[i], bit);
        trees[bit] = SegmentTree(bitValues);
    }
    for (; q > 0; --q) {
        int type;
        cin >> type;
        if (type == 1) {
            int where, value;
            cin >> where >> value;
            --where;
            for (int bit = 0; bit < MAX_BIT; ++bit)
                trees[bit].Update(where, GetBit(value, bit));
        } else {
            int from, to;
            cin >> from >> to;
            --from;
            --to;
            int answer = 0;
            for (int bit = 0; bit < MAX_BIT; ++bit)
                answer = (answer + 1LL * (1LL << bit) * trees[bit].Query(from, to)) % MOD;
            cout << answer << "\n";
        }
    }
    return 0;
}