Principi i final X55887

Teniu una seqüència buida, a la qual li podeu anar afegint números per la dreta o per l’esquerra. En qualsevol moment se us pot demanar quin és el primer o l’últim element de la seqüència.

Donada una sèrie d’instruccions de 6 tipus diferents:

• 1 x (afegeix l’element x a l’esquerra)

• 2 x (afegeix l’element x a la dreta)

• 3 (elimina l’element de l’esquerra)

• 4 (elimina l’element de la dreta)

• 5 (indica quin és l’element de l’esquerra)

• 6 (indica quin és l’element de la dreta)

Digues quines són les respostes de les instruccions del tipus 5 i 6. Se’t garanteix que no s’intentaran eliminar elements que no existeixin i que no se’t demanarà imprimir un element que no existeixi (És a dir, si la seqüència és buida la següent instrucció serà del tipus 1 o 2).

Entrada

L’entrada consisteix en diversos casos, hi ha com a molt $100$ casos. Cada cas comença amb una l’ínia amb un enter $1 \leq n \leq10^6$ a continuació apareixen $n$ línies, cada una amb una instrucció.

Se’t garanteix que la suma de totes les $n$ és $\leq 2 \cdot 10^6$ i que a la seqüència mai hi haurà més de $10^5$ elements.

Tots els elements $a_i$ compleixen: $0 \leq a_i \leq 10^9$.

Sortida

Per a cada instrucció del tipus 5 i 6 indica quin és l’element corresponent, imprimint una resposta per línia. A més, entre casos imprimeix 10 guions.