Dat je niz od n brojeva. Nad nizom se izvršavaju, jedan za drugim, m upita jednog od sledeća dva tipa:

• 1 i - seče trenutni niz posle i-tog elementa i zatim drugi deo niza (od (i + 1)-vog elementa do kraja) stavlja na početak, pri čemu se dobija novi niz od n elemenata. Npr. za niz 5 3 10 8 8, upit '1 2' daje 5 3 | 10 8 8 → 10 8 8 | 5 3 → 10 8 8 5 3.
• 2 j - treba odgovoriti koji se broj nalazi na j-toj poziciji u trenutnom nizu.

Odgovoriti na sve upite tipa 2.

Ulaz:

(Ulazni podaci se nalaze u datoteci upiti.in.) U prvom redu ulazne datoteke nalaze se 2 prirodna broja n i m koji predstavljaju, redom, broj elemenata niza i broj upita (1 ≤ n, m ≤ 10⁵). Sledeći red sadrži n celih brojeva - elemente niza u datom redosledu (svi elementi su iz [0, 10⁹]). Sledećih m redova sadrže upite već opisanog formata: 'a b' gde je a ∈ {1, 2} i 1 ≤ b ≤ n. Upiti se izvršavaju u redosledu datim na ulazu.

Izlaz:

(Izlazne podatke upisati u datoteku upiti.out) Za svaki upit tipa 2 iz ulazne datoteke ispisati u novi red izlazne datoteke odgovor na taj upit (odgovore ispisivati u odgovarajućem redosledu). Postojaće bar jedan upit tipa 2.

Primer:

5 4
5 3 10 8 8
2 3
1 2
1 4
2 3

10
8

Objašnjenje.

Na trećoj poziciji u početnom nizu je broj 10. Posle dva sećenja niz postaje 3 10 8 8 5. Na trećoj poziciji u ovom nizu je broj 8.

Napomena.

U 30% test primera biće n, m ≤ 10³.

#include <cstdlib>
#include <cstdio>

const int MaxN = 100010;
const int MaxM = 100010;

int n, m, a, b, x[MaxN], sol[MaxM];
int startIndex;

int main() {

  FILE* inFile = fopen("upiti.in", "r");
  FILE* outFile = fopen("upiti.out", "w");

  fscanf(inFile, "%d%d", &n, &m);

  // indeksiramo niz od 0 jer je tako lakse
  for (int i = 0; i < n; i++)
    fscanf(inFile, "%d", &x[i]);

  startIndex = 0;

  for (int i = 0; i < m; i++) {
    fscanf(inFile, "%d%d", &a, &b);
    if (a == 1)
      startIndex = (startIndex + b) % n;
    else
      fprintf(outFile, "%d\n", x[(startIndex + b - 1) % n]);
  }

  fclose(inFile);
  fclose(outFile);
}

const
  MaxN = 100010;
  MaxM = 100010;

var
  inFile, outFile : text;
  n, m, a, b, startIndex, i : longint;
  x : array[0..MaxN] of longint;
  sol : array[0..MaxM] of longint;

begin
  
  assign(inFile, 'upiti.in');
        assign(outFile, 'upiti.out');
  reset(inFile); rewrite(outFile);
  read(inFile, n, m);

  // indeksiramo niz od 0 jer je tako lakse
        for i := 0 to n - 1 do
    read(inFile, x[i]);

  startIndex := 0;

  for i := 1 to m do begin
          read(inFile, a, b);
          if (a = 1) then startIndex := (startIndex + b) mod n
                     else writeln(outFile, x[(startIndex + b - 1) mod n]);
        end;

  close(inFile);
  close(outFile);

end.