XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: computador.x, onde x deve ser c, cpp, java, js ou py

Computador

Uma grande empresa está construindo uma nova arquitetura de computadores que permita a execução eficiente de duas instruções especiais de soma. O computador possui N posições de memória, endereçadas de 1 a N, e cada posição pode guardar um inteiro maior ou igual a zero. Inicialmente, todas as posições contêm o valor zero. As instruções especiais de soma são:

  • FRENTE i V: Dado o endereço i, 1 ≤ i ≤ N, e um valor positivo V, o computador deve somar V na posição i, V-1 em i+1, V-2 em i+2, etc, enquanto o valor a ser somando for maior do que zero e a posição for menor ou igual a N;
  • TRÁS i V: Dado o endereço i, 1 ≤ i ≤ N, e um valor positivo V, o computador deve somar V na posição i, V-1 em i-1, V-2 em i-2, etc, enquanto o valor a ser somando for maior do que zero e a posição for maior ou igual a 1.

Por exemplo, para N=16, uma possível sequência de instruções é dada abaixo:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

FRENTE 4 8

0 0 0 8 7 6 5 4 3 2 1 0 0 0 0 0

TRÁS 16 3

0 0 0 8 7 6 5 4 3 2 1 0 0 1 2 3

TRÁS 2 12

11 12 0 8 7 6 5 4 3 2 1 0 0 1 2 3

FRENTE 8 7

11 12 0 8 7 6 5 11 9 7 5 3 2 2 2 3

Além disso, o computador possui a instrução IMPRIME i, que deve imprimir na saída o valor atual armazenado na posição i da memória.

Dados N e uma sequência de M instruções, seu programa deve imprimir, para cada instrução do tipo IMPRIME i, uma linha contendo o valor armazenado na posição de memória i no instante da execução da instrução.

Entrada

A primeira linha da entrada contém dois inteiros N e M, representando o número de posições de memória e o número de instruções, respectivamente. As M linhas seguintes contêm, cada uma, a descrição de uma instrução em uma de três formas possíveis: 1 I V, representando FRENTE I V; 2 I V, representando TRÁS I V; e 3 I, representando IMPRIME I.

Saída

Para cada instrução do tipo IMPRIME i, seu programa deve imprimir uma linha contendo um inteiro representando o valor armazenado na posição de memória i no instante da execução da instrução.

Restrições

  • 1 ≤ N ≤ 200000;
  • 1 ≤ M ≤ 200000;
  • 1 ≤ I ≤ N;
  • 1 ≤ V ≤ 200000;
  • Ao menos uma instrução será do tipo 3.

Informações sobre a pontuação

  • Em um conjunto de casos de teste somando 20 pontos, N ≤ 10000, M ≤ 10000 e V ≤ 10000;

Exemplos

Exemplos

Entrada
16 7
1 4 8
2 16 3
3 14
2 2 12
1 8 7
3 10
3 14
Saída
1
7
2
	

 

Entrada
200000 2
1 2345 193290
3 112230
Saída
83405
	

 

Promoção
logo sbc
Patrocínio
Apoio
Coordenação