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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=50005;
const int MAXM=100005;
int n,m,T;
namespace solve2
{
	struct edge{int x,y;}E[MAXM];
	int nx[5],cnt[5],ans[MAXM];
	void main()
	{
		if(n==2){pr2(-1);return ;}
		for(int i=1;i<=m;i++)E[i].x=read(),E[i].y=read();
		nx[1]=1;nx[2]=2;nx[3]=3;
		for(int i=m;i>=1;i--)
		{
			if(E[i].x<=3&&E[i].y<=3)
			{
				if(nx[E[i].x]==nx[E[i].y])ans[i]=1;
				else
				{
					memset(cnt,0,sizeof(cnt));
					for(int j=1;j<=3;j++)++cnt[nx[j]];
					if(cnt[nx[E[i].x]]>cnt[nx[E[i].y]])ans[i]=0,nx[E[i].x]=nx[E[i].y];
					else ans[i]=1,nx[E[i].y]=nx[E[i].x];
				}
			}
			else if(E[i].x<=3)ans[i]=1;
		}
		for(int i=1;i<=m;i++)putchar(ans[i]?'^':'v');puts("");
	}
}
namespace solve1
{
	bitset<MAXN> a[MAXN],tmp;
	struct edge{int x,y;}E[MAXM];
	int id[MAXN],ans[MAXM];
	void solve(int u)
	{
		id[u]=1;
		for(int i=m;i>=1;i--)
		{
			if((id[E[i].x]&id[E[i].y])||!(id[E[i].x]|id[E[i].y]))continue;
			if(id[E[i].x])ans[i]=1;id[E[i].x]|=1;id[E[i].y]|=1;
		}
		for(int i=1;i<=m;i++)putchar(ans[i]?'^':'v');puts("");
	}
	void main()
	{
		for(int i=1;i<=m;i++)E[i].x=read(),E[i].y=read();
		for(int i=1;i<=n;i++)a[i][i]=1;
		for(int i=m;i>=1;i--)a[E[i].x]=a[E[i].y]=a[E[i].x]|a[E[i].y];
		for(int i=1;i<=n;i++)tmp[i]=1;
		for(int i=1;i<=n;i++)tmp=tmp&a[i];
		if(!tmp.count()){pr2(-1);return ;}
		for(int i=1;i<=n;i++)if(tmp[i]){solve(i);return ;}
	}
}
int main()
{
	n=read();m=read();T=read();
	if(T==2){solve2::main();return 0;}
	else solve1::main();
	return 0;
}