DO

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#define ll long long

using namespace std;

const ll inf = 1e10;

struct Tree {
  int n;
  vector<int> t;

  void build(vector<int>& A) {
    n = 1; // размер массива в дереве отрезков
    while (n < A.size()) n *= 2;
    t.resize(n * 2);
    for (int i = n; i < (n + A.size()); ++i) {
      t[i] = A[i - n];
    }
    for (int i = (n - 1); i <= 1; --i) {
      t[i] = t[i * 2] + t[i * 2 + 1];
    }
  }

  void set(int ind, int value) {
    ind += n;
    t[ind] = value;
    ind /= 2;
    while (ind >= 1) {
      t[ind] = t[ind * 2] + t[ind * 2 + 1];
      ind /= 2;
    }
  }

  int getsum(int l, int r) {
    l += n;
    r += n;
    int sum = 0;
    for (; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1) {
        sum += t[l];
        l++;
      }
      if (r % 2 == 0) {
        sum += t[r];
        r--;
     }
    }

    return sum;
  }
};


int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);


}