Muncitorii de la cooperativa “Munca-n zadar” au la dispoziţie o ţeavă cu lungimea de N metri. Iniţial această ţeavă are culoarea C. Muncitorii pot tăia o bucată de ţeavă în două bucăţi de lungimi întregi şi revopsi cele două bucăţi. Muncitorii pot să se şi răzgândească şi să sudeze la loc două bucăţi înapoi în bucata mare din care au fost despărţite şi să o revopsească cu culoarea pe care o avea înainte de tăiere. Prin tăiere sau sudare bucăţile de ţevi nu se mută din locul lor iniţial şi deci o bucată de ţeavă poate fi identificată prin poziţia ei. Poziţia unei bucăţi de ţeavă este specificată prin distanţa dintre începutul ţevii iniţiale şi începutul bucăţii de ţeavă exprimată în metri.

Cerinţă

Lucraţi la această cooperativă şi trebuie să scrieţi un program care implementează următoarele comenzi:
• SPLIT( P, L, CL, CR) – bucata de ţeavă care începe la poziţia P va fi împărţită în două bucăţi mai mici, cea din stânga având mărimea L. Apoi bucata din stânga va fi colorată cu culoarea CL şi cea din dreapta cu culoarea CR. Se garantează că 0 < L < lungimea bucăţii de ţeavă care trebuie împărţită.
• UNDO(P) – bucata care începe la poziţia P se va resuda cu bucata imediat din dreapta ei. Se garantează că în momentul apelării acestei comenzi bucata imediat din dreapta ei este cea obţinută prin aceeaşi operaţie de tăiere în urma căreia a rezultat bucata de la poziţia P (chiar dacă se poate ca oricare dintre cele două bucăţi să fi fost tăiate şi resudate). Bucata rezultată se va recolora în culoarea pe care o avea înainte de tăiere.
• GETCOLOR(P) – se afişează culoarea bucăţii care începe la poziţia P.
Pentru toate comenzile, va exista o bucată de ţeavă care să înceapă la poziţia P.

Date de intrare

Fişierul culori.in conţine pe prima linie numerele N C M, separate printr-un spaţiu. Fiecare dintre următoarele M linii conţine o comandă. Comenzile sunt codificate astfel:

Date de ieşire

Fişierul culori.out va conţine atâtea linii câte comenzi GETCOLOR sunt, reprezentând culorile respective, în ordinea comenzilor GETCOLOR corespunzătoare.

Restricţii

• 1 <= N <= 524288 (219)
• 1 <= M <= 2 000 000
• Toate culorile au valori cuprinse între 0 şi 255 (inclusiv)
• Poziţiile vor fi numere întregi între 0 la N-1 (inclusiv)

Exemple

culori.in	culori.out
11 3 13 2 0 8 1 3 1 0 2 0 10 3 0 0 0 2 0 9 1 1 2 0 8 2 3 1 0 2 0 5 2 3 1 0 2 0 5 3 2 0 9 1 0 0 0	3 1 1

autor: Radu Berinde

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com