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:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)

ll N, M, T;

//ll A[50001/64 + 1][50001];
ll A[50001][50001/64 + 1];
int B[50001], cnt[50001];

int detect_ok(){ 
    rep(k, N/64 + 1){
        ll total = 0xffffffffffffffffLL;
        rep(i, N){
            //total &= A[k][i];
            total &= A[i][k];
        }
        rep(j, 64){
            if (total & (1LL << j)){
                return k * 64 + j;
            }
        }
    }
    return -1;
}

int main()
{
    cin >> N >> M >> T;
    vector<ll> X(M), Y(M);
    
    rep(i, M){
        ll x, y;
        cin >> x >> y;
        X[M - 1 - i] = x - 1;
        Y[M - 1 - i] = y - 1;
    }
    
    if (T == 1){
        
        //rep(i, N)A[i/64][i] = 1LL << (i%64);
        rep(i, N)A[i][i/64] = 1LL << (i%64);
        
        
        rep(i, M){
            ll x = X[i];
            ll y = Y[i];
            rep(k, N/64 + 1){
                //A[k][x] = A[k][x] | A[k][y];
                //A[k][y] = A[k][x];
                A[x][k] = A[x][k] | A[y][k];
                A[y][k] = A[x][k];

            }
        }
        //rep(i, N)
        //fprintf(stderr, "A[0][%d] = %d\n", i, A[0][i]);
        int res = detect_ok();
        if (res == -1){
            cout << -1;
            return 0;
        }
        string str = "";
        B[res] = 1;
        rep(i, M){
            ll x = X[i];
            ll y = Y[i];
            if (B[x] == 0){
                str += "v";
            } else {
                str += "^";
            }
            if (B[x] + B[y])B[x] = B[y] = 1;
        }
        reverse(str.begin(), str.end());
        cout << str;
        return 0;
    } 
    // T = 2;
    if (N == 2){
        cout << -1;
        return 0;
    }
    rep(i, N){
        B[i] = i;
        cnt[i]++;
    }
    string str = "";
    rep(i, M){
        ll x = X[i];
        ll y = Y[i];
        if (cnt[B[x]] >= 2){
            str += "v";
            cnt[B[x]]--;
            cnt[B[y]]++;
            B[x] = B[y];
        } else {
            str += "^";
            cnt[B[x]]++;
            cnt[B[y]]--;
            B[y] = B[x];
        }
    }
    reverse(str.begin(), str.end());
    cout << str;
        
    return 0;
}