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<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<map>
#include<vector>
using namespace std;
const pair<int,int> no=make_pair(-1,2333333);
#define N 50050
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,T,x[N<<1],y[N<<1],col[N<<1];
void Output(){
	for(int i=1;i<=m;++i){
		putchar(col[i]?'^':'v');
	}
	putchar('\n');
}
namespace Task_1{
	bitset<N> to[N];
	int ok[N];
	void Find(int k){
		ok[x[k]]=ok[y[k]]=1;
		for(int i=k-1;i>=1;--i){
			if(!ok[x[i]]&&!ok[y[i]])continue;
			if(ok[x[i]])col[i]=1;
			ok[x[i]]=ok[y[i]]=1;
		}
	}
	void Solve(){
		for(int i=1;i<=n;++i){
			to[i][i]=1;
		}
		for(int i=1;i<=m;++i){
			to[x[i]]=to[y[i]]=to[x[i]]|to[y[i]];
			if((int)to[x[i]].count()==n){
				Find(i);
				Output();
				return;
			}
		}
		printf("-1\n");
	}
}
namespace Task_2{
	vector<pair<int,int> > vec[N]; 
	void Solve(){
		if(n==2){
			puts("-1");return;
		}
		for(int i=m;i>=1;--i){
			vec[x[i]].emplace_back(y[i],i);
			vec[y[i]].emplace_back(x[i],i);
		}
		int A=x[1],B=y[1]+1;
		if(B>n)A=x[1]-1,B=y[1];
		if(A<1)A=x[1]+1,B=y[1];
		for(int i=1;i<=m;++i){
			while(!vec[A].empty()&&vec[A].back().second<=i)vec[A].pop_back();
			while(!vec[B].empty()&&vec[B].back().second<=i)vec[B].pop_back();
			auto tA=vec[A].empty()?no:vec[A].back();
			auto tB=vec[B].empty()?no:vec[B].back();
			bool rev=(tA.second<tB.second&&tA.first==B)||(tA.second>=tB.second&&tB.first==A);
			if(x[i]==A||y[i]==A){
				col[i]=rev^(x[i]==A);
				if(rev)A=(x[i]==A)?y[i]:x[i];
			}
			else if(x[i]==B||y[i]==B){
				col[i]=rev^(x[i]==B);
				if(rev)B=(x[i]==B)?y[i]:x[i];	
			}
		}
		Output();
	}
}
int main(){
	n=read(),m=read(),T=read();
	for(int i=1;i<=m;++i){
		x[i]=read(),y[i]=read();
	}
	if(T==1){
		Task_1::Solve();
	}
	else{
		Task_2::Solve();
	}
	return 0;
}