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 ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
template<class T> inline T popFirst(multiset<T> &a){
  T res = *(a.begin());
  a.erase(a.begin());
  return res;
}
template<class T> inline T getFirst(multiset<T> &a){
  return *(a.begin());
}
template<class T> inline T popFirst(set<T> &a){
  T res = *(a.begin());
  a.erase(a.begin());
  return res;
}
template<class T> inline T getFirst(set<T> &a){
  return *(a.begin());
}
struct unionFind{
  int *d;
  int N;
  int M;
  inline void malloc(const int n){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
  }
  inline void free(void){
    std::free(d);
  }
  inline void walloc(const int n, void **mem=&wmem){
    walloc1d(&d, n, mem);
    M = n;
  }
  inline void init(const int n){
    int i;
    N = n;
    for(i=(0);i<(n);i++){
      d[i] = -1;
    }
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    int t = a;
    int k;
    while(d[t]>=0){
      t=d[t];
    }
    while(d[a]>=0){
      k=d[a];
      d[a]=t;
      a=k;
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
    }
    else{
      d[b] += d[a];
      d[a] = b;
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](const int a){
    return d[a];
  }
  inline int size(int a){
    a = get(a);
    return -d[a];
  }
  inline int sizeList(int res[]){
    int i;
    int sz=0;
    for(i=(0);i<(N);i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
}
;
int N;
int M;
int T;
int X[100000];
int Y[100000];
char res[100002];
bitset<50000> bs[50000];
void solve1(){
  int i, k;
  unionFind uf;
  for(i=(0);i<(N);i++){
    bs[i].set(i);
  }
  for(i=(0);i<(M);i++){
    bs[X[i]] = bs[Y[i]] = (bs[X[i]] | bs[Y[i]]);
  }
  for(k=(0);k<(N);k++){
    if(bs[k].count() == N){
      uf.malloc(N);
      uf.init(N);
      for(i=(0);i<(M);i++){
        res[i] = '^';
      }
      for(i=(M)-1;i>=(0);i--){
        if(uf(X[i]) == uf(Y[i])){
          continue;
        }
        if(uf(X[i]) != uf(k) && uf(Y[i]) != uf(k)){
          continue;
        }
        if(uf(X[i]) == uf(k)){
          res[i] ='^';
        }
        else{
          res[i] ='v';
        }
        uf(X[i], Y[i]);
      }
      wt_L(res);
      wt_L('\n');
      return;
    }
  }
  wt_L(-1);
  wt_L('\n');
}
int flow[100000];
int cnv[100000];
int sz;
set<int> s[3];
void solve2(){
  int i;
  int st;
  int a[3];
  int k;
  int xx;
  int yy;
  int xi;
  int yi;
  if(N==2){
    wt_L(-1);
    wt_L('\n');
    return;
  }
  sz = N;
  for(i=(0);i<(N);i++){
    flow[i] = 1;
  }
  for(i=(0);i<(M);i++){
    res[i] = '^';
  }
  for(i=(0);i<(M);i++){
    if(sz > 3){
      if(flow[X[i]] == flow[Y[i]]  &&  flow[Y[i]] == 0){
        continue;
      }
      if(flow[X[i]] == flow[Y[i]]  &&  flow[Y[i]] == 1){
        flow[Y[i]] = 0;
        sz--;
        continue;
      }
      flow[X[i]] = 1;
      flow[Y[i]] = 0;
      continue;
    }
    st = i;
    break;
  }
  if(i==M){
    wt_L(res);
    wt_L('\n');
    return;
  }
  k = 0;
  for(i=(0);i<(N);i++){
    if(flow[i]){
      a[k++] = i;
    }
  }
  for(i=(0);i<(3);i++){
    cnv[a[i]] = i;
  }
  for(i=(st);i<(M);i++){
    if(flow[X[i]]==0 && flow[Y[i]]==1){
      res[i] = 'v';
    }
  }
  for(i=(st);i<(M);i++){
    if(flow[X[i]] && flow[Y[i]]){
      xx = cnv[X[i]];
      yy = cnv[Y[i]];
      s[xx].insert(i);
      s[yy].insert(i);
    }
  }
  for(i=(0);i<(3);i++){
    s[i].insert(1073709056);
  }
  for(i=(st);i<(M);i++){
    if(flow[X[i]] && flow[Y[i]]){
      xx = cnv[X[i]];
      yy = cnv[Y[i]];
      popFirst(s[xx]);
      popFirst(s[yy]);
      xi = getFirst(s[xx]);
      yi = getFirst(s[yy]);
      if(xi >= yi){
        res[i] ='^';
      }
      else{
        res[i] ='v';
      }
    }
  }
  wt_L(res);
  wt_L('\n');
}
int main(){
  wmem = memarr;
  rd(N);
  rd(M);
  rd(T);
  {
    int gEg5UqEA;
    for(gEg5UqEA=(0);gEg5UqEA<(M);gEg5UqEA++){
      rd(X[gEg5UqEA]);X[gEg5UqEA] += (-1);
      rd(Y[gEg5UqEA]);Y[gEg5UqEA] += (-1);
    }
  }
  if(T==1){
    solve1();
  }
  else{
    solve2();
  }
  return 0;
}
// cLay varsion 20191227-1

// --- original code ---
// int N, M, T, X[1d5], Y[1d5];
// char res[100002];
// 
// 
// bitset<50000> bs[50000];
// void solve1(){
//   unionFind uf;
// 
//   rep(i,N) bs[i].set(i);
//   rep(i,M) bs[X[i]] = bs[Y[i]] = (bs[X[i]] | bs[Y[i]]);
// 
//   rep(k,N) if(bs[k].count() == N){
//     uf.malloc(N);
//     uf.init(N);
//     rep(i,M) res[i] = '^';
// 
//     rrep(i,M){
//       if(uf(X[i]) == uf(Y[i])) continue;
//       if(uf(X[i]) != uf(k) && uf(Y[i]) != uf(k)) continue;
//       res[i] = if[uf(X[i]) == uf(k), '^', 'v'];
//       uf(X[i], Y[i]);
//     }
// 
//     wt(res);
//     return;
//   }
// 
//   wt(-1);
// }
// 
// int flow[1d5], cnv[1d5], sz;
// set<int> s[3];
// void solve2(){
//   int st, a[3], k;
//   int xx, yy, xi, yi;
// 
//   if(N==2) wt(-1), return;
// 
//   sz = N;
//   rep(i,N) flow[i] = 1;
//   rep(i,M) res[i] = '^';
// 
//   rep(i,M){
//     if(sz > 3){
//       if(flow[X[i]] == flow[Y[i]] == 0) continue;
//       if(flow[X[i]] == flow[Y[i]] == 1) flow[Y[i]] = 0, sz--, continue;
//       flow[X[i]] = 1;
//       flow[Y[i]] = 0;
//       continue;
//     }
//     st = i; break;
//   }
// 
//   if(i==M) wt(res), return;
// 
//   k = 0;
//   rep(i,N) if(flow[i]) a[k++] = i;
//   rep(i,3) cnv[a[i]] = i;
//   rep(i,st,M) if(flow[X[i]]==0 && flow[Y[i]]==1){
//     res[i] = 'v';
//   }
//   rep(i,st,M) if(flow[X[i]] && flow[Y[i]]){
//     xx = cnv[X[i]];
//     yy = cnv[Y[i]];
//     s[xx].insert(i);
//     s[yy].insert(i);
//   }
//   rep(i,3) s[i].insert(int_inf);
//   rep(i,st,M) if(flow[X[i]] && flow[Y[i]]){
//     xx = cnv[X[i]];
//     yy = cnv[Y[i]];
//     popFirst(s[xx]);
//     popFirst(s[yy]);
//     xi = getFirst(s[xx]);
//     yi = getFirst(s[yy]);
//     res[i] = if[xi >= yi, '^', 'v'];
//   }
//   wt(res);
// }
// 
// {
//   rd(N,M,T,(X--,Y--)(M));
//   if(T==1) solve1();
//   else     solve2();
// }