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:
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// gp_hash_table<int, int> mapka;

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int n,m,t;
vector<vector<PII>> d;
vector<int> res;
vector<int> edge;
vector<int> kon;
int add_edge(int a,int b){
  d[a].PB({b,SZ(edge)});
  edge.PB(1);
  d[b].PB({a,SZ(edge)});
  edge.PB(0);
  return SZ(edge) - 1;
}
vector<int> vis;
bool dfs(int v){
  if(vis[v])return 0;
  vis[v] = 1;
  if(kon[v])return 1;
  for(PII el:d[v]){
    if(edge[el.SE]){
      if(dfs(el.FI)){
        edge[el.SE] = 0;
        edge[el.SE ^ 1] = 1;
        return 1;
      }
    }
  }
  return 0;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n >> m >> t;
  if(t == 2){
    d.resize(n + m * 4);
    res.resize(m);
    vector<int> ak(n);
    R(i,n)ak[i] = i;
    int id = n;
    R(i,m){
      int a,b;
      cin >> a >> b;
      a--;b--;
      add_edge(ak[a], id);
      add_edge(ak[b], id);
      add_edge(id,id+1);
      res[i] = add_edge(id+1,id+2);
      add_edge(id+1,id+3);
      ak[a] = id + 2;
      ak[b] = id + 3;
      id += 4;
    }
    kon.resize(SZ(d));
    R(i,n)kon[ak[i]] = 1;
    vis.resize(SZ(d));
    R(i,2){
      bool ok = 0;
      R(j,SZ(vis))vis[j] = 0;
      R(j,n){
        if(dfs(j)){
          ok = 1;
          break;
        }
      }
      if(!ok){
        cout << "-1\n";
        return 0;
      }
    }
    R(i,m){
      if(edge[res[i]]){
        cout << "^";
      }else
        cout << "v";
    }
    cout << "\n";
  }else{
    
#define res ressss
#define t tt
    typedef bitset<50001> bs;
    vector<bs> t(n);
    bs all;
    vector<int> a(m),b(m);
    R(i,n)t[i][i] = 1;
    R(i,m){
      cin >> a[i] >> b[i];
      a[i]--;b[i]--;
      t[a[i]] = t[b[i]] = t[a[i]]|t[b[i]];
    }
    R(i,n)all[i] = 1;
    R(i,n){
      if(t[i] == all){
        string res(m,'^');
        vector<int> ok(n);
        ok[i] = 1;
        for(int j = m - 1; j >= 0; j--){
          if(ok[a[j]]){
            res[j] = '^';
            ok[b[j]] = 1;
          }else if(ok[b[j]]){
            res[j] = 'v';
            ok[a[j]] = 1;
          }
        }
        cout << res << "\n";
        return 0;
      }
    }
    cout << "-1\n";
  }
}