#include "monede.h"
#include <bits/stdc++.h>
using namespace std;

struct matrice {
    Raport m[2][2];
};

matrice multiply(const matrice &a, const matrice &b) {
    matrice ret = {Raport(0, 0), Raport(0, 0), Raport(0, 0), Raport(0, 0)};
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                ret.m[i][k] += a.m[i][j] * b.m[j][k];
    return ret;
}

int N;
vector<matrice> aint;

auto id = matrice{Raport(1, 1), Raport(0, 1), Raport(0, 1), Raport(1, 1)};

void init(int n, const Raport rs[]) {
    N = n;
    aint.resize(4 * n + 1, id);
    for (int i = 0; i < n; ++i)
        aint[i + n] =
            matrice{Raport(1, 1) - rs[i], rs[i], rs[i], Raport(1, 1) - rs[i]};
    for (int i = n - 1; i > 0; --i)
        aint[i] = multiply(aint[2 * i], aint[2 * i + 1]);
}

matrice query(int nod, int st, int dr, int qst, int qdr) {
    if (qdr < st)
        return id;
    if (dr < qst)
        return id;

    if (qst <= st && dr <= qdr)
        return aint[nod];

    return multiply(query(2 * nod, st, (st + dr) / 2, qst, qdr),
                    query(2 * nod + 1, (st + dr) / 2 + 1, dr, qst, qdr));
}

Raport solve(int x, int y) { return Raport(1, 2); }
