#include <bits/stdc++.h>
//#define int long long
#define sz(x) (x).size() 
#define all(x) (x).begin(), (x).end()
#define pb push_back 
#define sonic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//const int MAX=2e17+5;
const int abi=1e6;
using namespace std; 
int n,t=1; 
long long tree[abi * 4];
int a[abi];
void build_tree(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];    //сумма отрезка из одного элемента равна этому элементу
    } else {
        //tm - средний элемент отрезка.
        //отрезок разбивается на два отрезка [tl; tm], [tm + 1; tr]
        int tm = (tl + tr) / 2;
        build_tree(v * 2, tl, tm);
        build_tree(v * 2 + 1, tm + 1, tr);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
}
void update(int idx, int val, int v, int tl, int tr) {
    //вариант 1
    if (idx <= tl && tr <= idx) {    //То же, что и idx == tl == tr
        a[idx] = val;
        tree[v] = val;
        return;
    }

    //вариант 2
    if (tr < idx || idx < tl) {
        return;
    }

    //вариант 3
    int tm = (tl + tr) / 2;
    update(idx, val, v * 2,     tl,     tm);
    update(idx, val, v * 2 + 1, tm + 1, tr);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

long long get_sum(int l, int r, int v, int tl, int tr) {
    //вариант 1
    if (l <= tl && tr <= r) {
        return tree[v];
    }

    //вариант 2
    if (tr < l || r < tl) {
        return 0;
    }

    //вариант 3
    int tm = (tl + tr) / 2;
    return get_sum(l, r, v * 2,     tl,     tm)
         + get_sum(l, r, v * 2 + 1, tm + 1, tr);
}
void x( ){
    
}signed main(){sonic 
    //cin>>t; 
    while(t--){ 
    x();
    }
    return 0; 
}



  








