Fişierul intrare/ieşire:	mdluffxor.in, mdluffxor.out	Sursă	AGM 2019, runda finala,ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Patrick Sava •xtreme77
Timp execuţie pe test	3.5 sec	Limită de memorie	512000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mdluffxor

MDLuffXor este un spirit liber si vrea sa fie regele piratilor din spatiu. Din pacate, intai are de facut putina munca administrativa. MDLuffXor trebuie sa se ocupe de diverse siruri de cufere cu comori, care sunt gasite intr-o anumita ordine. Fiecare sir contine unul sau mai multe cufere, iar fiecare cufar contine o comoara, cu o valoare un numar natural ce nu depaseste 10⁹. Acestea sunt construite de inamicul sau, maleficul Xoro, ca sa il incurce – insa, Xoro nu stie, in niciun moment, valorile comorilor din cufere. Fiecare sir de cufere este fie:

• Un singur cufar, a carui valoare ii este necunoscuta lui Xoro. Aceasta valoare este generata aleatoriu.
• Un sir creat de Xoro, ale carui valori sunt egale cu o concatenare a doua siruri de cufere anterioare.
• Un sir creat de Xoro, ale carui valori sunt egale cu prefixul unui sir de cufere anterior.
• Un sir creat de Xoro, ale carui valori sunt egale cu sufixul unui sir de cufere anterior.

Totusi, este garantat ca orice sir va avea cel mult 10¹⁸ cufere. In orice moment, maleficul Xoro il poate intreba pe MDLuffXor care este valoarea a celei de a K-a mai valoroasa comoara (de la cea mai valoroasa la cea mai putin valoroasa) intr-un sir anume. Xoro nu se foloseste de aceasta informatie cand va construi urmatoarele cerinte. Fiind date sirurile de cufere, gaseste raspunsurile intrebarilor lui Xoro.

Date de intrare

Fişierul de intrare mdluffxor.in va contine pe primul rand un numar natural Q. Inputul va fi codificat intr-un mod neobisuit. Pentru a-l decoda, intai initializati o variabila int last, cu valoarea 0. Pe urmatoarele Q randuri vei gasi una din urmatoarele:

1. 1 x, insemnand ca un sir ce contine un singur cufar, cu o valoare egala cu x, apare.
2. 2 x y, insemnand ca un nou sir, egal cu concatenarea celor de al (X XOR last)-lea si de al (Y XOR last)-lea siruri apare.
3. 3 x l, insemnand ca un nou sir, egal cu prefixul de lungime l XOR last al celui de al (X XOR last)-lea sir apare.
4. 4 x l, insemnand ca un nou sir, egal cu sufixul de lungime l XOR last al celui de al $(X XOR last)-lea sir apare.
5. 5 x K, reprezentand o intrebare pusa de Xoro: "Care este a K-a (*nu* K XOR last) cea mai valoroasa comoara din al (x XOR last)-lea sir?”. Dupa o astfel de interogare, daca raspunsul a fost ans, last se actualizeaza cu valoarea (17 * last + ans) mod 666.013

Sirurile sunt indexate incepand de la 1, in ordinea in care apar. Se garanteaza ca in input se va face referire doar la siruri care exista deja.

Date de ieşire

În fişierul de ieşire mdluffxor.out se vor afisa raspunsurile la intrebarile lui Xoro, in ordine, pe randuri diferite.

Restricţii

• K ≤ 400
• Q ≤ 200.000

Exemplu

Cum se trimit solutii?