Problem: A balancing network is an abstract device built up of N wires, thought of as running from left to right, and M balancers that connect pairs of wires. The wires are numbered from 1 to N from top to bottom, and the balancers are numbered from 1 to M from left to right. Balancer i connects wires x_i and y_i (x_i < y_i).

pic1-small-2acea94b.png

Each balancer must be in one of two states: up or down.

Consider a token that starts moving to the right along some wire at a point to the left of all balancers. During the process, the token passes through each balancer exactly once. Whenever the token encounters balancer i, the following happens:

* If the token is moving along wire x_i and balancer i is in the down state, the token moves down to wire y_i and continues moving to the right.
* If the token is moving along wire y_i and balancer i is in the up state, the token moves up to wire x_i and continues moving to the right.
* Otherwise, the token doesn't change the wire it's moving along.



Let a state of the balancing network be a string of length M, describing the states of all balancers. The i-th character is `^` if balancer i is in the up state, and `v` if balancer i is in the down state.

A state of the balancing network is called uniforming if a wire w exists such that, regardless of the starting wire, the token will always end up at wire w and run to infinity along it. Any other state is called non-uniforming.

You are given an integer T (1 \le T \le 2). Answer the following question:

* If T = 1, find any uniforming state of the network or determine that it doesn't exist.
* If T = 2, find any non-uniforming state of the network or determine that it doesn't exist.



Note that if you answer just one kind of questions correctly, you can get partial score.

Constraints

* 2 \leq N \leq 50000
* 1 \leq M \leq 100000
* 1 \leq T \leq 2
* 1 \leq x_i < y_i \leq N
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N M T
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print any uniforming state of the given network if T = 1, or any non-uniforming state if T = 2. If the required state doesn't exist, output `-1`.

Examples

Input

4 5 1
1 3
2 4
1 2
3 4
2 3


Output

^^^^^


Input

4 5 2
1 3
2 4
1 2
3 4
2 3


Output

v^^^^


Input

3 1 1
1 2


Output

-1


Input

2 1 2
1 2


Output

-1

Solution (in CPP):

Solution:
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int x[100000],y[100000];
bitset<50000> bs[50000],poss;
char ans[100000];
int poss2[3][3];
vector<pair<int,char> > sol[3][3];
int main() {
    int i;
    int N,M,T;
    scanf("%d %d %d",&N,&M,&T);
    for (i = 0; i < M; i++) scanf("%d %d",&x[i],&y[i]),x[i]--,y[i]--;

    int j;
    if (T == 1) {
        for (i = 0; i < N; i++) bs[i][i] = 1;
        for (i = 0; i < M; i++) bs[x[i]] |= bs[y[i]],bs[y[i]] |= bs[x[i]];
        int cand = -1;
        for (i = 0; i < N; i++) {
            if (bs[i].count() == N) {
                cand = i;
                break;
            }
        }
        if (cand == -1) printf("-1\n");
        else {
            poss[cand] = 1;
            for (j = M-1; j >= 0; j--) {
                if (poss[x[j]] && !poss[y[j]]) ans[j] = '^',poss[y[j]] = 1;
                else if (!poss[x[j]] && poss[y[j]]) ans[j] = 'v',poss[x[j]] = 1;
                else ans[j] = '^';
            }
            for (j = 0; j < M; j++) printf("%c",ans[j]);
            printf("\n");
        }
    }
    else {
        if (N == 2) {
            printf("-1\n");
            return 0;
        }
        for (i = 0; i < 3; i++) {
            for (j = i+1; j < 3; j++) poss2[i][j] = 1;
        }
        for (i = 0; i < M; i++) {
            if (y[i] < 3) {
                poss2[x[i]][y[i]] = 0;
                j = x[i]^y[i]^3;
                if (poss2[min(x[i],j)][max(x[i],j)]) {
                    poss2[min(y[i],j)][max(y[i],j)] = 2;
                    sol[min(y[i],j)][max(y[i],j)].pb(mp(i,'v'));
                }
                if (poss2[min(y[i],j)][max(y[i],j)] == 1) {
                    poss2[min(x[i],j)][max(x[i],j)] = 1;
                    sol[min(x[i],j)][max(x[i],j)].pb(mp(i,'^'));
                }
                else if (poss2[min(y[i],j)][max(y[i],j)] == 2) poss2[min(y[i],j)][max(y[i],j)] = 1;
            }
        }
        int a,b;
        for (i = 0; i < 3; i++) {
            for (j = i+1; j < 3; j++) {
                if (poss2[i][j]) {
                    a = i,b = j;
                    break;
                }
            }
            if (j < N) break;
        }
        for (i = M-1; i >= 0; i--) {
            if (y[i] >= 3) ans[i] = '^';
            else {
                int p = lower_bound(sol[a][b].begin(),sol[a][b].end(),mp(i,'\0'))-sol[a][b].begin();
                if ((p < sol[a][b].size()) && (sol[a][b][p].first == i)) {
                    ans[i] = sol[a][b][p].second;
                    if (a == x[i]) a = y[i];
                    else if (a == y[i]) a = x[i];
                    if (b == x[i]) b = y[i];
                    else if (b == y[i]) b = x[i];
                    if (a > b) swap(a,b);
                }
                else {
                    if (x[i] == a) ans[i] = '^';
                    else if (x[i] == b) ans[i] = '^';
                    else if (y[i] == a) ans[i] = 'v';
                    else if (y[i] == b) ans[i] = 'v';
                    else ans[i] = '^';
                }
            }
        }
        for (i = 0; i < M; i++) printf("%c",ans[i]);
        printf("\n");
    }

    return 0;
}