Dato je ne jedno, već dva skladišta. Jedno je doduše prazno ali dobrodođe u vremenskim neprilikama kakve samo što nisu.

Natalija, iskusni vozač viljuškara, je sama sebi smislila zadatak da sortira sve kutije u punom skladištu, i ne samo punom već i jako tesnom. Kutije se prostiru u nizu počev od prednjih vrata skladišta pa sve do zadnjeg vrata skladišta i numerisane su brojevima ~A_i~. Sve što je u njenoj moći je da ulaskom na prednja vrata svojim viljuškarom uzme prvu kutiju ili ulaskom na zadnja vrata uzme poslednju kutiju. Nakon toga ona može prebaciti tu kutiju u bilo koje od 2 skladišta sa bilo prednje bilo zadnje strane (svakog trenutka se očekuje vremenska nepogoda pa ne sme rizikovati da ostavi po koju napolju).

Formalnije, ako su se zadesile u nekom trenutku kutije u prvom skladištu i označimo ih sa ~X_1, X_2, ..., X_p~, i kutije u drugom skladištu koje označimo sa ~Y_1, Y_2, ..., Y_q~ (na početku je ~q=0~ jer je drugo skladište prazno), Natalija može uzeti bilo koju od ~4~ kutije ~X_1, X_p, Y_1, Y_q~ i premestiti je na početak ili kraj niza ~X~, ili na početak ili kraj niza ~Y~.

Kao što smo rekli, Natalija želi da sortira sve kutije koje su inicijalno u prvom skladištu po njihovoj numeraciji ~A_i~ neopadajuće, koristeći se gore opisanom pravilom u svakom koraku. Na kraju razvrstavanja, sve kutije se moraju naći u prvom skladištu, dok će drugo, nažalost, opet ostati prazno.

Svaka pomoć u rešavanju joj je i više nego dobrodošla.

Opis ulaza

U prvoj liniji standardnog ulaza nalazi se broj ~N~ (~1 \le N \le 10^3~) koji označava broj kutija koje se na početku nalaze u prvom skladištu. U drugoj liniji nalazi se ~N~ prirodnih brojeva razdvojenih razmakom ~A_{1}, A_{2}, ..., A_{N}~ ~(1 \le A_{i} \le 10^9)~, gde ~A_{i}~ označava broj koji se nalazi na ~i~-toj kutiji.

Opis izlaza

U prvoj liniji ispisati broj premeštanja ~T~ koje će Natalija izvršiti. U svakoj od narednih ~T~ linija ispisati opis ~i~-tog premeštanja u formatu:

~Poc_i~ ~PocPrilaz_i~ ~Kraj_i~ ~KrajPrilaz_i~

gde su ~Poc_i~ broj početnog skladišta (odakle uzima kutiju) i ~Kraj_i~ (broj skladišta gde spušta kutiju) iz skupa ~\{0, 1\}~. Brojem ~0~ se obeležava prvo skladište (na početku puno), a brojem ~1~ se obeležava drugo skladište (na početku prazno). ~PocPrilaz_i~ i ~KrajPrilaz_i~ označavaju sa koje strane se prilazi skladištu viljuškarem. Ove vrednosti su iz skupa ~\{P, Z\}~, gde ~P~ označava prilaz sa prednje strane, a ~Z~ prilaz sa zadnje.

Da bi se dobili poeni na određenom test primeru potrebno je da broj premeštanja ~T \le maxT~ (u suprotnom se dobija ~0~ na tom test primeru). Pogledati vrednosti ~maxT~ ispod u delu sa podzadacima. Takođe, potrebno je da posle ispisanog niza komandi, sve kutije u prvom skladištu budu sortirane i da drugo skladište ostane prazno. Svaka komanda mora predstavaljati validno premeštanje (ne sme se uzeti kutija iz nekog skladišta ako je u tom trenutku prazno). Isto, ako bilo koja promenljiva ~Poc_i~, ~PocPrilaz_i~, ~Kraj_i~ ili ~KrajPrilaz_i~ nije iz gore pomenutih skupova, dobija se 0 poena na tom test primeru.

Primeri

4
2 1 2 5

4
0 P 1 P
0 Z 1 Z
1 P 0 Z
1 P 0 Z

Objašnjenje prvog test primera:

0

[2 1 2 5]
[]

2 skladišta i inicijalni raspored kutija u njima

1

[1 2 5]
[2]

Prebacujemo iz 0. skladišta prednju kutiju u 1. skladište na prednja vrata.

2

[1 2]
[2 5]

Prebacujemo iz 0. skladišta zadnju kutiju u 1. skladište na zadnja vrata.

3

[1 2 2]
[5]

Prebacujemo iz 1. skladišta prednju kutiju u 0. skladište na zadnja vrata.

4

[1 2 2 5]
[]

Prebacujemo iz 1. skladišta prednju kutiju u 0. skladište na zadnja vrata.

Kao što se da primetiti, brojevi u ~0.~ skladištu su sada sortirani u ~4~ koraka.

Ograničenja, bodovanje i podzadaci

~1 \le N \le 10^3~, ~1 \le A_{i} \le 10^9~

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 10 poena: ~1 \le A_{i} \le 3~, ~maxT=10^4~
  
• U test primerima vrednim 20 poena: ~maxT=10^6~
  
• U test primerima vrednim 40 poena: ~maxT=2*10^4~
  
• U test primerima vrednim 30 poena: ~maxT=10^4~