#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NX 100000

int c[NX], N, M, queryRes, K;

int terminalZeros(int num)
{
	int zeros = 0;
	while ((num | 1 << zeros) != num) {
		zeros++;
	}

	return zeros;
}

int sumInterval(int poz)
{
	int sum = c[poz];
	while (poz > 0)
	{
		int zeros = terminalZeros(poz);
		poz -= 1 << zeros;
		sum += c[poz];
	}

	return sum;
}

void query(int st, int dr)
{
	int sum1 = sumInterval(st - 1);

	int sum2 = sumInterval(dr);

	queryRes = sum2 - sum1;
}

void update(int poz, int val)
{
	c[poz] += val;

	while (poz < N)
	{
		int zeros = terminalZeros(poz);

		poz += 1 << zeros;
		c[poz] += val;
	}
}

void determineMinK(int sum)
{
	int st = 1, dr = N, mij = 0;
	K = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		int val = sumInterval(mij);
		if (sum == val)
		{
			K = mij;
			break;
		}

		if (sum > val) 
		{
			st = mij + 1;
		} 
		else if (sum < val)
		{
			dr = mij - 1;
		}
	}
}

void createPowTwoPoz(int i, int val)
{
	c[i] = val;

	int st = 1, dr = i;
	int mij = 0;

	while (st < dr) 
	{
		mij = (st + dr) / 2;
		c[i] += c[mij];
		st = mij + 1;
	}
}
 
int main()
{
    int op, an, bn, val;
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
  
    scanf("%d %d", &N, &M);
   
    for (int i = 1; i <= N; i++)
    {
		scanf("%d", &val);
		if (i % 2)
		{
			c[i] = val;
		} 
		else
		{
			if ((i & (i - 1)) == 0)
			{
				createPowTwoPoz(i, val);	
			} else if (i % 4 == 2)
			{
				c[i] = val + c[i - 1];
			} else if (i % 4 == 0)
			{
				c[i] = val + c[i - 1] + c[i - 2];
			}
			
		}
    }
 
    for (int i = 1; i <= M; i++)
    {
        scanf("%d", &op);
   
        switch (op)
        {
        case 0:
			scanf("%d %d\n", &an, &bn);
            update(an, bn);
            break;
        case 1:
			scanf("%d %d\n", &an, &bn);
            query(an, bn);
			printf("%d\n", queryRes);
            break;
		case 2:
			scanf("%d\n", &an);
			determineMinK(an);
			printf("%d\n", K);
			break;
        }
    }
 
}