Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int mod = 1e9 + 9;
int add(int x, int y) { return (x + y) % mod; }
int sub(int x, int y) { return (x - y + mod) % mod; }
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int modpow(int n, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = mul(res, n);
        n = mul(n, n);
        k >>= 1;
    }
    return res;
}
int divide(int a, int b) { return mul(a, modpow(b, mod - 2)); }

struct fenwick_point { 
    int n;
    vector<int> fenw;
    fenwick_point(int _n) : n(_n + 5) { fenw.resize(n); }

    void increment(int i, int v) {
        for (++i; i < n; i += (i & -i)) fenw[i] = add(fenw[i], v);
    }
    int query(int i) {
        int res = 0;
        for (++i; i > 0; i -= (i & -i)) res = add(res, fenw[i]);
        return res;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& u : a) cin >> u;
    
    set<int> invalid;
    for (int i = 0; i < n; i++) if (a[i] > 1) invalid.insert(i);
    invalid.insert(n);

    vector<int> pow_2(n + 1), invpow_2(n + 1);
    pow_2[0] = 1, pow_2[1] = 2;
    invpow_2[0] = 1, invpow_2[1] = divide(1, 2);

    for (int i = 2; i <= n; i++) {
        pow_2[i] = mul(pow_2[i - 1], pow_2[1]);
        invpow_2[i] = mul(invpow_2[i - 1], invpow_2[1]);
    }

    fenwick_point f(n + 1);
    for (int i = 0; i < n; i++) {
        f.increment(i, mul(pow_2[n - i], a[i]));
    }

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

        if (type == 1) {
            int i, x;
            cin >> i >> x;
            --i;
            f.increment(i, sub(0, mul(pow_2[n - i], a[i])));

            a[i] = 1 & (a[i] ^ x);

            invalid.erase(i);
            f.increment(i, mul(pow_2[n - i], a[i]));
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            int j = *invalid.lower_bound(l);
            if (j <= r) {
                cout << "Impossible\n";
                continue;
            }
            int res = f.query(r);
            if (l) res = sub(res, f.query(l - 1));
            // it is multiplied by pow_2[n - r], 
            cout << mul(res, invpow_2[n - r]) << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    tt = 1, tc = 1; // cin >> tt;
    while (tt--) solve(), tc++;
}