Problem E
Elapid Errands

Ferðalag snáksins í sýniinntaki.

Snákurinn Karl er í holu sinni í hnitinu $(0, 0)$ á óendanlegu plani. Hann vill fara í heimsókn á punktana $(x_1, y_1), (x_2, y_2), \dots , (x_N, y_N)$. Hann vill fara í heimsóknirnar í röðinni sem punktarnir eru gefnir og hann vill enda í punktinum $(x_N, y_N)$. Í einu skrefi getur hann fært sig upp, niður, til vinstri eða hægri. En þar sem hann er mjög langur snákur getur hann aldrei farið í sama punktinn tvisvar.

Verkefni þitt er að finna runu skrefa sem Karl getur tekið svo hann nái heimsóknum sínum í réttri röð og fari aldrei í sama punkt tvisvar. Punktarnir $(x_i, y_i)$ voru valdir slembið með jöfnum líkum.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $N$ ($1 \leq N \leq 20)$, fjöldi punkta sem Karl vill heimsækja.

Næst fylgja $N$ línur með tveimur heiltölum $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^4$) hver.

Utan við sýniinntakið verða $100$ prófunartilfelli, öll með $N = 20$. Manhattan-fjarlægðin milli sérhverra tveggja punkta (þar á meðal upphafspunktsins $(0, 0)$) verður í minnsta lagi $20$. Með tilliti til þessarra takmarkana voru punktarnir valdir $(x_i, y_i)$ slembið með jöfnum líkum.

Athugið að sýniinntakið uppfyllir ekki fjarlægðartakmörk. Lausn þín þarf ekki að leysa sýniinntakið til að vera samþykkt.

Úttak

Prentið streng sem samanstendur af stöfunum ‘<’, ‘>’, ‘^’, ‘v’. Þetta er listi skrefanna sem þú vilt að Karl taki til að ná öllum heimsóknum sínum í réttri röð án þess að fara í neinn punkt tvisvar. Strengurinn má mest vera af lengd $2 \cdot 10^6$.

2
0 10
5 0

^^^^^^^^^^>>vvv>v>vvv<vvv>>