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 ≤ n ≤10⁶ a continuació apareixen n línies, cada una amb una instrucció.

Se’t garanteix que la suma de totes les n és ≤ 2 · 10⁶ i que a la seqüència mai hi haurà més de 10⁵ elements.

Tots els elements a_i compleixen: 0 ≤ a_i ≤ 10⁹.

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.