<Segment Trees without Lazy> TEMPLATE

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

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>

const int MOD = 1000000007;

const ll MAX = 2005;

#define read1(a) int a; scanf("%d", &a)
#define read2(a, b) int a, b; scanf("%d %d", &a, &b)
#define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
#define readgs(n) F0R(i, n) { scanf("%c", &arr[i]); }

#define f first
#define s second

int arr[4*MAX];
int tree[4*MAX];
void build(int node, int a, int b) {
    if (a == b) { tree[node] = arr[a]; return; }
    build(2*node, a, (a+b)/2);
    build(2*node+1, (a+b)/2 + 1, b);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

void update(int node, int a, int b, int i, int value) {
    if (a > i || b < i) { return; }
    if (a == b) { tree[node] += value; return; }
    update(2*node, a, (a+b)/2, i, value);
    update(2*node+1, (a+b)/2 + 1, b, i, value);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

int query(int node, int a, int b, int i, int j) {
    if (a > j || b < i) { return -1; }
    if (i <= a && b <= j) { return tree[node]; }
    int x = query(2*node, a, (a+b)/2, i, j);
    int y = query(2*node+1, (a+b)/2 + 1, b, i, j);
    return max(x, y);
}