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>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
#define N 50009
using namespace std;

int read(); ll readll();
int n,m,cnt,type,a[N<<1],b[N<<1]; bitset<N> C,c[N];
char ans[N<<1],ch[N<<2]; bool bo[N];
pair<pii,int> last[N<<2]; map<pair<pii,int>,int> mp;
bool check(int x,int y,int u,int v){
	return min(x,y)==min(u,v) && max(x,y)==max(u,v);
}
void opt(pair<pii,int> o){
	if (!o.se) return;
	opt(last[mp[o]]); putchar(ch[mp[o]]);
}
void dfs(int x,int y,int k,int u,int v,char c){
	if (x>y) swap(x,y); if (x==y) return;
	auto o=mpr(mpr(x,y),k);
	if (mp[o]) return; mp[o]=++cnt;
	last[cnt]=mpr(mpr(u,v),k-1); ch[cnt]=c;
	if (k==m){ opt(o); puts(""); exit(0); }
	k++;
	if (check(x,y,a[k],b[k])) return;
	if (x==a[k] || x==b[k]){
		dfs(x,y,k,x,y,(x==a[k]?'^':'v'));
		dfs(x^a[k]^b[k],y,k,x,y,(x==a[k]?'v':'^'));
		return;
	}
	if (y==a[k] || y==b[k]){
		dfs(x,y,k,x,y,(y==a[k]?'^':'v'));
		dfs(x,y^a[k]^b[k],k,x,y,(y==a[k]?'v':'^'));
	}
	dfs(x,y,k,x,y,'^');
}
int main(){
	scanf("%d%d%d",&n,&m,&type);
	int i,j;
	for (i=1; i<=m; i++) scanf("%d%d",&a[i],&b[i]);
	if (type==2){
		if (n==2){ puts("-1"); return 0; }
		int x=a[1],y=b[1],z=1;
		while (z==x || z==y) z++;
		dfs(x,z,1,0,0,'^'); dfs(y,z,1,0,0,'v');
		return 0;	
	}
	for (i=1; i<=n; i++) c[i].set(i);
	for (i=1; i<=m; i++){
		C=c[a[i]];
		c[a[i]]|=c[b[i]]; c[b[i]]|=C;
	}
	for (i=1; i<=n; i++) C.set(i);
	for (i=1; i<=n; i++) if ((c[i]^C).none()){
		bo[i]=1;
		for (j=m; j; j--) if (bo[a[j]]){
			ans[j]='^'; bo[b[j]]=1;
		} else{
			ans[j]='v'; bo[a[j]]=bo[b[j]];
		}
		puts(ans+1); break;
	}
	if (i>n) puts("-1");
	return 0;
}

int read(){
	int x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}
ll readll(){
	ll x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}