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;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N, M, T;
int x[100000], y[100000];
string ans;
bool Reach[100000];

void solve1() {
    vector<bitset<50000>> bits;
    bits.resize(N);
    for(int i = 0; i < N; i++) {
        bits[i][i] = true;
    }
    for(int i = 0; i < M; i++) {
        bits[x[i]] |= bits[y[i]];
        bits[y[i]] |= bits[x[i]];
    }
    int ansidx = -1;
    for(int i = 0; i < N; i++) {
        if(bits[i].count() == N) ansidx = i;
    }
    if(ansidx == -1) {
        cout << -1 << endl;
        return;
    }
    Reach[ansidx] = true;
    for(int e = M - 1; e >= 0; e--) {
        if(Reach[x[e]]) ans[e] = '^';
        else ans[e] = 'v';
        Reach[x[e]] |= Reach[y[e]];
        Reach[y[e]] |= Reach[x[e]];
    }
    cout << ans << endl;
}

vector<int> Connect[50000];
int Index[50000];

void solve2() {
    if(N == 2) {
        cout << -1 << endl;
        return;
    }
    for(int i = 0; i < M; i++) {
        Connect[x[i]].push_back(y[i]);
        Connect[y[i]].push_back(x[i]);
    }
    for(int i = 0; i < N; i++) {
        Reach[i] = true;
    }
    int num = N;
    for(int e = 0; e < M; e++) {
        assert(Connect[x[e]][Index[x[e]]] == y[e]);
        assert(Connect[y[e]][Index[y[e]]] == x[e]);
        if(num > 3) {
            ans[e] = '^';
            num -= Reach[x[e]];
            num -= Reach[y[e]];
            Reach[x[e]] |= Reach[y[e]];
            Reach[y[e]] = false;
            num += Reach[x[e]];
            num += Reach[y[e]];
        } else {
            num -= Reach[x[e]];
            num -= Reach[y[e]];
            if(Index[x[e]] + 1 < Connect[x[e]].size() and Reach[Connect[x[e]][Index[x[e]] + 1]]) {
                int to = Connect[x[e]][Index[x[e]]+1];
                //cerr << x[e] << " " << y[e] << " " << to << endl;
                /*
                if(Connect[to].size() <= Index[to]) {
                    for(int i = 0; i <= 1e9; i++) cout << "A" << endl;
                }
                */
                int newidx = Index[to];
                if(to == y[e]) newidx++;
                if(Connect[to][newidx] == x[e]) {
                    ans[e] = 'v';
                    Reach[y[e]] |= Reach[x[e]];
                    Reach[x[e]] = false;
                } else {
                    ans[e] = '^';
                    Reach[x[e]] |= Reach[y[e]];
                    Reach[y[e]] = false;
                }
            } else {
                ans[e] = '^';
                Reach[x[e]] |= Reach[y[e]];
                Reach[y[e]] = false;
            }
            num += Reach[x[e]];
            num += Reach[y[e]];
        }
        Index[x[e]]++;
        Index[y[e]]++;
        /*
        for(int i = 0; i < N; i++) cerr << Index[i] << " ";
        cerr << endl;
        */
    }
    cout << ans << endl;
}


int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> T;
    for(int i = 0; i < M; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    ans = string(M, 'a');
    if(T == 1) solve1();
    else solve2();
    return 0;
}