bool verbose = false;

class Prymitywna {
    public:

    vector<char> slowo;
    Prymitywna(string slowo) {
        for(char c : slowo)
            this->slowo.push_back(c);
    }

    int32_t num_of_right_sequences(int a, int b) {
        int32_t res[2][2];
        int32_t res_new[2][2];
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++) {
                res[i][j] = 0;
            }

        int32_t nowy[2][2];

        for(int nr = a; nr <= b; nr++) {
            for(int i = 0; i < 2; i++)
                for(int j = 0; j < 2; j++)
                    nowy[i][j] = 0;

            if (slowo[nr] == 'G')
                nowy[1][1] = 1;
            else
                nowy[0][0] = 1;

            calculate_nums_for_two_connected(res, nowy, res_new);
            for(int i = 0; i < 2; i++)
                for(int j = 0; j < 2; j++)
                    res[i][j] = res_new[i][j];
        }

        int32_t kacowy = 0;
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                kacowy = suma(kacowy, res[i][j]);
            }
        }
        return kacowy;
    }

    void przekrec_odcinek(int a, int b) {
        vector<char> wek;
        for(int nr = a; nr <= b; nr++) {
            wek.push_back(slowo[nr]);
        }

        for(int i = 0; i < wek.size(); i++)
            slowo[b - i] = wek[i];
    }
};

string generate_word(int n) {
    string res = "";
    for(int i = 0; i < n; i++)
        if (rand() % 2 == 0)
            res += "G";
        else
            res += "R";
    return res;
}

int generuj_int(int n) {
    return rand() % n;
}

void generuj_pare(int & a, int & b, int n) {
    while(true) {
        a = generuj_int(n);
        b = generuj_int(n);
        if (a <= b)
            return;
    }
}

void testuj(int n, int num_przes, int num_testow_na_przes) {
    string slowo = generate_word(n);
    // TODO tutaj wasza struktura wchodzi
    Drzewo drz(slowo, n);
    Prymitywna prym(slowo);

    for(int i = 0; i < num_przes; i++) {
        //cout << "\n\n\n" << endl << "i = " << i << endl;

        for(int j = 0; j < num_testow_na_przes; j++) {
            //cout << "\n\n\n" << endl << "j = " << j << endl;
            int a, b;
            generuj_pare(a, b, n);
            if (drz.num_of_right_sequences(a, b) != prym.num_of_right_sequences(a, b)) {
                cout << "\n\n fail ab " << a << " " << b << "\n drzewo daje " << drz.num_of_right_sequences(a, b) << "a powinno" <<
                        prym.num_of_right_sequences(a, b);
                cout << "\nchwilowo slowo byc powinno ";
                for (char c : prym.slowo)
                    cout << c;
                cout << endl;
                cout << "\n\n a drzewo jest teraz takie \n";
                drz.wypisz_sie();

                cout << "\n\n teraz puszczam jeszcze raz tylko verbose ab " << a << " " << b << endl;
                verbose = true;
                drz.num_of_right_sequences(a, b);
                assert(false);
            }
        }

        int a,b;
        generuj_pare(a, b, n);
        //cout << "\n\nprzestawienie ab " << a << " " << b << endl << endl;
        drz.przekrec_odcinek(a, b);
        prym.przekrec_odcinek(a, b);
    }
}

/*
// przyklad uzycia
int main()
{
    // ustalamy seed
    srand(3563);


    // tutaj zrobimy kolumne legionistow o dlugosci 10,
    // odbijemy w niej odcinek 2 1000 razy
    // po kazdym takim odbiciu 1000 razy sprawdzimy czy daje dobre wyniki powstala struktura
    testuj(10, 1000, 1000);

    //cout << "\n\nkoniec pliku\n";
    return 0;
}
*/