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>
#define N 50011
#define M 800011
#define bits 60
#define K 400011
using namespace std;
int n,m,type,total1,S,T;
int bian[M],slast[M],dis[M],h[M],in[M],out[M],types[M],v[M];
int ans[M],last[M],x[M],y[M],next[M],head[M],father[M],edge[M];
long long all[N],state[100011][N/bits+3];
void insert(int x,int y)
{
	total1++;
	next[total1]=head[x];
	head[x]=total1;
	edge[total1]=y;
}
void insert1(int x,int y,int z,int z1)
{
//	printf("%d %d %d %d\n",bian[x],bian[y],z,z1);
	total1++;
	next[total1]=head[x];
	head[x]=total1;
	edge[total1]=y;
	v[total1]=z;
	types[total1]=z1;
	int t=x;x=y;y=t;z=0;
	total1++;
	next[total1]=head[x];
	head[x]=total1;
	edge[total1]=y;
	v[total1]=z;
	types[total1]=z1;
}
int getfather(int x)
{
	if (father[x]==x) return x;
	father[x]=getfather(father[x]);
	return father[x];
}
bool bfs()
{
	int l=1,r=1;
	h[l]=S;
	for (int i=1;i<=T;i++) dis[i]=1e9;
	dis[S]=1;
	while (l<=r)
	{
		int u=h[l];
		for (int i=head[u];i;i=next[i])
		{
			int y=edge[i];
			if (v[i]>0&&dis[y]>dis[u]+1)
			{
				dis[y]=dis[u]+1;
				if (y==T) return true;
				r++;
				h[r]=y;
			}
		}
		l++;
	}
	return false;
}
int dinic(int k,int flow)
{
	if (k==T) return flow;
	int rest=flow;
	for (int i=head[k];i;i=next[i])
	{
		int y=edge[i];
		if (v[i]>0&&dis[y]==dis[k]+1)
		{
			int cost=v[i];
			if (cost>rest) cost=rest;
			int pay=dinic(y,cost);
			if (pay==0) dis[y]=0;
			rest-=pay;
			v[i]-=pay;v[i^1]+=pay;
			if (rest==0) break;
		}
	}
	return flow-rest;
}
int main()
{
	scanf("%d%d%d",&n,&m,&type);
	for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
	if (type==1)
	{
		for (int i=1;i<=m;i++)
		{
			insert(i,last[x[i]]);insert(i,last[y[i]]);	
			last[x[i]]=i;last[y[i]]=i;
		}
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=n/bits+1;j++)
			{
				for (int k=head[i];k;k=next[k])
				{
					int y=edge[k];
					state[i][j]|=state[y][j];
				}
			}
			for (int j=1;j<=n/bits+1;j++)
			{
				if ((j-1)*bits<x[i]&&x[i]<=j*bits)
					state[i][j]|=((1ll<<(x[i]-(j-1)*bits-1)));
				if ((j-1)*bits<y[i]&&y[i]<=j*bits)
					state[i][j]|=((1ll<<(y[i]-(j-1)*bits-1)));
			}
		}
		for (int i=1;i<=n/bits+1;i++)
		{
			for (int j=1;j<=bits;j++)
				if ((i-1)*bits+j<=n) all[i]=all[i]+(1ll<<(j-1));
		}
		int start=-1;
		for (int i=1;i<=m;i++)
		{
			bool if_all=true;
			for (int j=1;j<=n/bits+1;j++)
			{
				if (state[i][j]!=all[j])
				{
					if_all=false;break;
				}
			}
			if (if_all)
			{
				start=i;break;
			}
		}
		if (start==-1)
		{
			printf("-1\n");return 0;
		}
		for (int i=1;i<=n;i++) father[i]=i;
		ans[start]=0;
		father[x[start]]=y[start];
		for (int i=start-1;i>=1;i--)
		{
			int u=getfather(x[i]);
			int v=getfather(y[i]);
			if (u==v) ans[i]=1;
			else
			{
				if (u==y[start]) ans[i]=1;
				else	ans[i]=0;
				if (u==y[start]) father[v]=u;
				if (v==y[start]) father[u]=v;
			}
		}
		for (int i=1;i<=m;i++) 
			if (ans[i]==1) printf("^");
			else	printf("v");
		return 0;
	}
	total1=1;
	S=0,T=m*2+n+1;
	int num=0;
	for (int i=1;i<=m;i++) 
	{
		num++;in[i]=num;
		num++;out[i]=num;
	}
	for (int i=1;i<=m;i++) bian[in[i]]=bian[out[i]]=i;
	for (int i=m*2+1;i<=T;i++) bian[i]=i;
	total1=1;
	for (int i=1;i<=m;i++)
	{
		insert1(out[last[x[i]]],in[i],1,slast[x[i]]);
		insert1(out[last[y[i]]],in[i],1,slast[y[i]]);
		last[x[i]]=i;slast[x[i]]=1;
		last[y[i]]=i;slast[y[i]]=2;
	}	
	for (int i=1;i<=n;i++) insert1(out[last[i]],m*2+i,1,slast[i]);
	for (int i=1;i<=n;i++) insert1(m*2+i,T,1,3);
	for (int i=1;i<=m;i++) 
		insert1(in[i],out[i],1,3);
	int maxflow=0,flow=0;
	while (bfs())
	{
		while (flow=dinic(S,1e9)) 
		{
			maxflow+=flow;
			if (maxflow>=2) break;
		}
		if (maxflow>=2) break;
	}
	if (maxflow<=1)
	{
		printf("-1\n");return 0;
	}
	for (int i=1;i<=total1;i++)
	{
		if (i%2==1) continue;
		if (v[i]==0&&v[i^1]>0&&types[i]!=3&&types[i]!=0)
			ans[bian[edge[i^1]]]=types[i]-1;
	}
	for (int i=1;i<=m;i++) 
		if (ans[i]==0) printf("^");
		else	printf("v");
}