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;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,M,T; cin >> N >> M >> T;
	using P = pair<int,int>;
	V<P> es(M);
	rep(i,M){
		int x,y; cin >> x >> y; x--,y--;
		es[i] = P(x,y);
	}
	if(T == 1){
		using BS = bitset<50000>;
		V<BS> b(N);
		rep(i,N) b[i][i] = true;
		per(i,M){
			show(b);
			int x = es[i].fs, y = es[i].sc;
			b[x] |= b[y];
			b[y] |= b[x];
		}
		rep1(i,N-1) b[0] &= b[i];
		rep(tar,N) if(b[0][tar]){
			string ans(M,'.');
			V<bool> is(N); is[tar] = true;
			per(i,M){
				int x = es[i].fs, y = es[i].sc;
				if(is[x]){
					ans[i] = '^';
				}else{
					ans[i] = 'v';
				}
				if(is[x] || is[y]) is[x] = is[y] = true;
			}
			show(b);
			show(tar);
			show(is);
			assert(is == V<bool>(N,true));
			cout << ans << endl;
			return 0;
		}
		cout << -1 << endl;
		return 0;
	}else{
		if(N == 2){
			cout << -1 << endl;
			return 0;
		}
		VV<bool> dp(M+1,V<bool>(8));
		VV<int> from(M+1,V<int>(8,-1));
		VV<char> which(M+1,V<char>(8,'?'));
		dp[0][7] = true;
		auto Set = [&](int i,int s,int ns,char c){
			if(dp[i+1][ns]) return;
			dp[i+1][ns] = true;
			from[i+1][ns] = s;
			which[i+1][ns] = c;
		};
		rep(i,M){
			int x = es[i].fs, y = es[i].sc;
			rep(s,8) if(dp[i][s]){
				{	//up
					int ns = s;
					if(y<=2){
						if(s&1<<y){
							ns ^= 1<<y;
							ns |= 1<<x;
						}
					}
					Set(i,s,ns,'^');
				}
				{	//down
					int ns = s;
					if(y<=2){
						if(s&1<<x){
							ns ^= 1<<x;
							ns |= 1<<y;
						}
					}
					Set(i,s,ns,'v');
				}
			}
		}
		rep(s,8) if(__builtin_popcount(s) >= 2 && dp[M][s]){
			string ans(M,'.');
			for(int i=M;i>0;i--){
				ans[i-1] = which[i][s];
				s = from[i][s];
			}
			cout << ans << endl;
			return 0;
		}
		assert(false);
	}
}