Problem E
Elapid Errands
Languages
en
is
Carl the snake is in his burrow at the point $(0,0)$ in an infinite plane. He wants to visit the points $(x_1, y_1), (x_2, y_2), \dots , (x_N, y_N)$. These points must be visited in the order they are given, and Carl must end up at the point $(x_N, y_N)$. In one move, he can move one step up, down, left, or right. However, since he is a very long snake, he can never visit the same point more than once.
Your task is to find a sequence of moves such that Carl visits all the points in order, and never visits any point more than once. The points $(x_i, y_i)$ were generated uniformly at random.
Input
The first line contains one integer $N$ ($1 \leq N \leq 20$), the number of points you must visit.
The following $N$ lines each contain two integers $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^4$).
Apart from the sample, there will be $100$ testcases, all with $N = 20$. The (manhattan) distance between any two of the points (including the starting point $(0,0)$) will be at least $20$. Within these constraints, the points $(x_i, y_i)$ were generated uniformly at random.
Note that the sample does not satisfy the distance requirement. Your solution does not need to solve the sample to get accepted.
Output
Print a string consisting of the characters ‘<’, ‘>’, ‘^’, ‘v’. This is the list of moves you should make so that you visit all the points in order without ever going to the same point more than once. The string must have length at most $2 \cdot 10^6$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 0 10 5 0 |
^^^^^^^^^^>>vvv>v>vvv<vvv>> |
