Interval 0/1 Bit

//    ||  ||   //\\    || \\   |||||||
//    ||  ||  //  \\   ||  \\  ||
//    |||||| ||    ||  || ||   |||||     KRISNA
//    ||  || ||    ||  || \\   ||
//    ||  || ||    ||  ||  \\  |||||||

/**
 * Author           : Dipu Kumar Mohanto (Dip)
 *                    CSE, BRUR.
 *                    Batch - 6
 *
 * Problem          : Interval 0/1 Bit
 * Algorithm        :
 * Complexity       :
 * Category         :
 *
 * Difficulty       :
 * Source           :
 *
 * Verdict          :
 *
 * Code url         :
 *
 * Date             :
 * E-mail           : dipukumarmohanto1@gmail.com
 **/

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <memory.h>
#include <functional>
#include <numeric>

using namespace:: std;


#define READ                                 freopen("in.txt", "r", stdin)
#define WRITE                                freopen("out.txt", "w", stdout)

#define FAST                                 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)



#define All(v)                              v.begin(), v.end()
#define SZ(a)                               a.size()
#define Sort(v)                             sort(All(v))
#define ED(v)                               Sort(v), v.erase(unique(All(v), v.end())
#define Common(a, b)                        Sort(v), Sort(b), a.erase(set_intesection(All(a), All(b), a.begin(), a.end()))
#define UnCommon(a, b)                      Sort(v), Sort(b), a.erase(set_symmetric_difference(All(a), All(b), All(a)))


#define max3(a, b, c)                       max(a, max(b, c))
#define min3(a, b, c)                       min(a, min(b, c))
#define maxAll(v)                          *max_element(All(v))
#define minAll(v)                          *min_element(All(v))


#define AllUpper(a)                         transform(All(a), a.begin(), :: toupper)
#define AllLower(a)                         transform(All(a), a.begin(), :: tolower)
#define Rev(a)                              reverse(All(a))


#define memo(a, b)                          memset(a, b, sizeof(a))

#define ff                                  first
#define ss                                  second
#define pb                                  push_back
#define mk                                  make_pair

#define inf2                               1 << 28

template <typename T>string toString (T Number)    { stringstream st; st << Number; return st.str(); }
int toInteger (string s)                           { int p; istringstream st(s); st>>p ; return p;}



//int dr[] = {1, -1, 0, 0};               // 4 Direction
//int dc[] = {0, 0, 1, -1};

//int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
//int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};

//int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
//int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};


#define Exp                                exp(1.0)
#define PIE                                2*acos(0.0)
#define Sin(a)                             sin(((a)*PI)/180.0)
#define mod                                1000000007
#define EPS                                1e-9

#define sqr(a)                             ((a)*(a))
#define gcd(a,b)                           __gcd(a,b)
#define lcm(a,b)                           (a*(b/gcd(a,b)))


typedef long long          ll;

const int mx = 100000 + 5;



int num_0[mx];
int num_1[mx];


pair <int, int> f(int n)
{
    int one = 0;
    int zero = 0;

    while (n)
    {
        int rem = n%2;

        if (rem)
            one++;

        else
            zero++;

        n /= 2;
    }
    return make_pair(zero, one);
}

void calc()
{
    for (int i=0; i<mx-4; i++)
    {
        pair <int, int> n = f(i);

        num_0[i] = n.ff;
        num_1[i] = n.ss;
    }
}

#define PII               pair <int, int>


struct treeNode {
    int One, Zero;

    void assignLeaf(int num)
    {

        if (!num_0[num])
            Zero = 0;

        else
            Zero = num;

        if (!num_1[num])
            One = num;

        else
            One = num;
    }


    void Marge(treeNode& left, treeNode& right) {
        int one_left = left.One;
        int zero_left = left.Zero;

        int one_right = right.One;
        int zero_right = right.Zero;


        if (num_0[zero_left] > num_0[zero_right]) {
            Zero = zero_left;
        }

        else if (num_0[zero_left] < num_0[zero_right]) {
            Zero = zero_right;
        }

        else if (num_0[zero_left] == num_0[zero_right]) {
            Zero = max(zero_left, zero_right);
        }

        if (num_1[one_left] > num_1[one_right]) {
            One = one_left;
        }

        else if (num_1[one_left] < num_1[one_right]) {
            One = one_right;
        }

        else if (num_1[one_left] == num_1[one_right]) {
            One = min(one_left, one_right);
        }
    }



    treeNode Query(treeNode& left, treeNode& right) {
        int one_left = left.One;
        int zero_left = left.Zero;

        int one_right = right.One;
        int zero_right = right.Zero;

        if (zero_left == -1 && one_left==-1)
        {
            treeNode t;
            t.Zero = zero_right;
            t.One =  one_right;
        }

        if (zero_right == -1 && one_right==-1)
        {
            treeNode t;
            t.Zero = zero_left;
            t.One =  one_left;
        }


        if (num_0[zero_left] > num_0[zero_right]) {
            Zero = zero_left;
        }

        else if (num_0[zero_left] < num_0[zero_right]) {
            Zero = zero_right;
        }

        else if (num_0[zero_left] == num_0[zero_right]) {
            Zero = max(zero_left, zero_right);
        }

        if (num_1[one_left] > num_1[one_right]) {
            One = one_left;
        }

        else if (num_1[one_left] < num_1[one_right]) {
            One = one_right;
        }

        else if (num_1[one_left] == num_1[one_right]) {
            One = min(one_left, one_right);
        }

        treeNode t;
        t.One = One;
        t.Zero = Zero;

        return t;
    }


    void updat(int num)
    {
        Zero = num;
        One = num;
    }




} tree[mx << 2];

treeNode Return() {
        treeNode t;

        t.One = -1;
        t.Zero = -1;

        return t;
}

int arr[mx];



void build_tree(int node, int a, int b)
{
    if (a>b)
        return;

    if (a==b)
    {
        tree[node].assignLeaf(arr[a]);

        return;
    }
    int left = node<<1;
    int right = left|1;
    int mid = (a+b)>>1;

    build_tree(left, a, mid);
    build_tree(right, mid+1, b);

    tree[node].Marge(tree[left], tree[right]);
}



treeNode query(int node, int a, int b, int i, int j)
{
    if (a>b || i>b || j<a)
        return Return();

    if (a>=i && b<=j)
        return tree[node];

    int left = node<<1;
    int right = node<<1|1;
    int mid = (a+b)>>1;


    treeNode left_part = query(left, a, mid, i, j);
    treeNode right_part = query(right, mid+1, b, i, j);

    treeNode res;

    res.Query(left_part, right_part);

    return res;
}


void update(int node, int a, int b, int i, int num)
{
    if (a>b || i>b || i<a)
        return;

    if (a>=i && b<=i)
    {
        treeNode t;
        t.One = num;
        t.Zero = num;

       // treeNode tt;
        //tt.Query(tree[node], t);

        tree[node].updat(num);


        return;
       // return tt;
    }
    int left = node<<1;
    int right = node<<1|1;
    int mid = (a+b)>>1;

    update(left, a, mid, i, num);
    update(right, mid+1, b, i, num);

    tree[node].Marge(tree[left], tree[right]);
}

int main()
{
    READ;


    calc();

    int n;
    cin >> n;

    for (int i=1; i<=n; i++)
        cin >> arr[i];

    build_tree(1, 1, n);

    int q;
    cin >> q;

    while (q--)
    {
        char op;
        int i, j;

        cin >> op;

        if (op == 'u')
        {
            int num;
            cin >> i >> num;

            update(1, 1, n, i, num);
        }

        if (op == 'q')
        {
            cin >> i >> j;

            if (i > j)
                swap(i, j);

            treeNode t = query(1, 1, n, i, j);

            int num;
            cin >> num;

            if (num == 0)
                cout << t.Zero << endl;

            else
                cout << t.One << endl;
        }
    }

}