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 unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<ll,ll>
#define poly vector<ll>
#define mem(a) memset((a),0,sizeof(a))
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ll rnd(){
	ull ans=0;
	For(i,0,4)ans=ans<<15^rand();
	return ans%((ull)1<<63);
}
const int N=50005,M=100005,K=256;
int n,m,x[M],y[M],vis[N],to[N];
char ans[M];
void GG(){
	puts("-1"); exit(0);
}
int main(){
	
	#ifdef Brollan
		freopen("1.in","r",stdin);
	#endif
	n=read(),m=read(); int T=read();
	double t=clock();
	if(T==1){
		static bitset<N> s[N];
		For(i,1,n)s[i][i]=1;
		For(i,1,m){
			x[i]=read(); y[i]=read();
			s[x[i]]=s[y[i]]=s[x[i]]|s[y[i]];
		}
		For(i,1,n)if(s[i].count()==n){
			vis[i]=1;
			Rep(j,m,1){
				//cout<<x[i]<<" "<<vis[x[i]]<<endl;
				if(vis[x[j]])ans[j]='^'; else ans[j]='v';
				vis[x[j]]=vis[y[j]]=vis[x[j]]|vis[y[j]];
			}
			cout<<(ans+1)<<endl; return 0;
		}	
	}else{
		static bitset<K+2> s[M][K+2];
		For(i,1,m){
			x[i]=read(); y[i]=read();
		}
		For(i,1,n)For(j,i+1,min(n,K))s[0][i][j]=s[0][j][i]=1;
		For(o,0,1000){
			int node=0;
			For(j,0,511)to[j]=0;
			For(j,0,min(255,n-1)){
				int t=rnd()%min(n,500)+1;
				while(to[t])t=rnd()%min(n,500)+1;
				to[t]=++node;
			}
			For(i,1,m){
				memcpy(s[i],s[i-1],sizeof(s[i]));
				int X=to[x[i]],Y=to[y[i]];
				if(to[X]&&to[Y]){
					s[i][Y]=s[i][X]=s[i][Y]|s[i][X];
					For(j,1,K)s[i][j][X]=s[i][j][Y]=s[i][j][X]|s[i][j][Y];
					s[i][X][Y]=s[i][Y][X]=s[i][X][X]=s[i][Y][Y]=0;
				}
			}
			For(X,1,n)For(Y,X+1,min(n,500))if(to[X]&&to[Y]&&s[m][to[X]][to[Y]]){
				Rep(i,m,1){
					if(s[i-1][to[X]][to[Y]]){
						if(X==x[i]||Y==x[i])ans[i]='^';
						else ans[i]='v';
					}else{
						if(X==x[i]||Y==x[i]){
							ans[i]='^';
							if(X==x[i])X=y[i]; else Y=y[i];
						}else{
							ans[i]='v';
							if(X==y[i])X=x[i]; else Y=x[i];
						}
					}
				}
				cout<<(ans+1)<<endl;
				exit(0);
			}
			if((clock()-t)/CLOCKS_PER_SEC>1.6)GG();
		}
	}
	GG();
}