#include <stdio.h>
#include <stdlib.h>
#define MAX 100001
#define in "aib.in"
#define out "aib.out"
int tree[4*MAX], numb[4*MAX];
void insert(int node, int left, int right, int poz, int value)
{
int m, t;
if (left >= right)
{
if (tree[node] == 0)
numb[node / 2]++;
tree[node] += value;
numb[node ] = 0;
}
else
{
m = (left + right) / 2;
t = numb[node];
if (poz <= m)
insert(2*node, left, m, poz, value);
else
insert(2*node+1, m+1, right, poz, value);
tree[node] = tree[2*node] + tree[2*node+1];
if (t != numb[node])
numb[node / 2]++;
}
}
int find(int node, int left, int right, int a, int b)
{
int x = 0, y = 0, m;
if (a <= left && b >= right)
return tree[node];
else
{
m = (left + right) / 2;
if (a <= m)
x = find(2*node, left, m, a, b);
if (b > m)
y = find(2 * node + 1, m + 1, right, a, b);
return x + y;
}
}
int sum(int node, int left_nodes,int total)
{
int x = 0;
if (tree[node] == total)
{
//printf("node %d value %d total %d\n", node, tree[node], total);
if (numb[node] == 0)
//leaf
return left_nodes + 1;
else
return left_nodes + numb[node];
}
else if (numb[node] == 0)
{
//printf("node %d value %d total %d\n", node, tree[node], total);
return -1;
}
else
{
//printf("node %d value %d total %d left %d right %d \n", node, tree[node], total, tree[2*node], tree[2*node+1]);
x = total - tree[2 * node];
if (tree[node] < total)
{
return -1;
}
else if (total <= tree[2 * node] )
return sum(2*node, left_nodes, total);
else if (x > tree[2 * node + 1])
return -1;
else
return sum(2*node+1, numb[2*node], x);
}
}
int main()
{
int a[MAX], n, i, z, m, x, y;
FILE *fin, *fout;
if ((fin = fopen(in, "r")) == NULL)
{
printf("Eroare \n");
exit(-1);
}
//read dimension of vectors
fscanf(fin, "%d%d", &n, &m);
//read the vectors
for (i = 1; i<=n ; i++)
{
fscanf(fin, "%d", &a[i]);
insert(1, 1, n, i, a[i]);
}
fout = fopen(out, "w");
/*
for (i = 0; i <= 2 * n + 1; i++)
printf("%d ", tree[i]);
printf("\n");
*/
for (i = 0; i < m; i++)
{
fscanf(fin, "%d%d", &x, &y);
if (x == 0)
{
fscanf(fin, "%d", &z);
insert(1, 1, n, y, z);
//printf("Interval [%d %d] are maximul %d\n", y, z, j);
}
else if (x == 1)
{
fscanf(fin, "%d", &z);
z = find(1, 1, n, y, z);
fprintf(fout, "%d\n", z);
/*for (j = 0; j <= 2 * n + 1; j++) find(int node, int left, int right, int a, int b)
printf("%d ", tree[j]);
printf("\n");*/
} else if (x == 2)
{
//printf("\n");
z = sum(1, 0, y);
fprintf(fout, "%d\n", z);
}
}
fclose(fin);
fclose(fout);
return 0;
}