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;

// N*M = 5,000,000,000 -> 5/8 GB
// N*N = 2,500,000,000 -> 2.5/8 GB

const int MAX_N = 50123;

int n, m, T;
vector<pair<int,int>> balancers;

void one() {
	vector<bitset<MAX_N>> mask(n);
	for(int i = 0; i < n; ++i) {
		mask[i][i] = 1;
	}
	for(pair<int,int> p : balancers) {
		mask[p.first] |= mask[p.second];
		mask[p.second] = mask[p.first];
	}
	int last = -1;
	for(int i = 0; i < n; ++i) {
		if((int) mask[i].count() == n) {
			last = i;
			break;
		}
	}
	if(last == -1) {
		puts("-1");
		exit(0);
	}
	vector<bool> good(n);
	good[last] = true;
	string s(m, '?');
	for(int i = m - 1; i >= 0; --i) {
		int x = balancers[i].first;
		int y = balancers[i].second;
		if(good[x]) {
			s[i] = '^';
			good[y] = true;
		}
		else if(good[y]) {
			s[i] = 'v';
			good[x] = true;
		}
		else {
			s[i] = 'v';
		}
	}
	printf("%s\n", s.c_str());
}

vector<pair<int, pair<int,int>>> parent[1000][1000];
vector<vector<bool>> good;
void can_go(int a, int b, int c, int d, int tim) {
	if(good[a][b] && !good[c][d]) {
		good[c][d] = true;
		parent[c][d].push_back({tim, {a, b}});
	}
}

void two() {
	assert(T == 2);
	set<pair<int,int>> set;
	for(pair<int,int> p : balancers) {
		set.insert(p);
	}
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			if(!set.count({i, j})) {
				string s;
				for(pair<int,int> p : balancers) {
					assert(p != make_pair(i, j));
					if(p.first == i || p.first == j) {
						s += '^';
					}
					else if(p.second == i || p.second == j) {
						s += 'v';
					}
					else {
						s += 'v';
					}
				}
				printf("%s\n", s.c_str());
				cerr << "pair is " << i << " " << j << endl;
				exit(0);
			}
		}
	}
	cerr << "N is for sure small!" << endl;
	assert(n < 1000);
	good.resize(n, vector<bool>(n));
	// vector<vector<bool>> good(n, vector<bool>(n));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(i != j) {
				good[i][j] = true;
			}
		}
	}
	
	for(int tim = 0; tim < m; ++tim) {
		pair<int,int> p = balancers[tim];
		int x = p.first;
		int y = p.second;
		good[x][y] = good[y][x] = false;
		for(int i = 0; i < n; ++i) {
			if(i != x && i != y) {
				// can_go(i, x, i, x, tim);
				can_go(i, x, i, y, tim);
				can_go(i, y, i, x, tim);
				can_go(x, i, y, i, tim);
				can_go(y, i, x, i, tim);
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			assert(good[i][j] == good[j][i]);
			if(i < j && good[i][j]) {
				string s(m, '?');
				// printf("%d %d\n", i, j);
				// printf("YES %d %d\n", i, j);
				int tim = m;
				auto move_down_to = [&](int new_time) { // tim-1 ... new_time
					for(int b = tim - 1; b >= new_time; --b) {
						int x = balancers[b].first;
						int y = balancers[b].second;
						assert(make_pair(min(i, j), max(i, j)) != make_pair(x, y));
						assert(s[b] == '?');
						if(x == i || x == j) {
							s[b] = '^';
						}
						else if(y == i || y == j) {
							s[b] = 'v';
						}
						else {
							s[b] = 'v';
						}
					}
				};
				while(!parent[i][j].empty()) {
					pair<int, pair<int,int>> pp = parent[i][j].back();
					if(pp.first > tim) {
						parent[i][j].pop_back();
					}
					else {
						assert(pp.first < tim);
						move_down_to(pp.first + 1);
						tim = pp.first;
						assert(0 <= tim && tim < m);
						assert(s[tim] == '?');
						assert((i == pp.second.first) != (j == pp.second.second));
						if(make_pair(i, j) < pp.second) {
							s[tim] = '^';
						}
						else {
							s[tim] = 'v';
						}
						tie(i, j) = pp.second;
						// printf("%d %d time=%d\n", i, j, tim);
					}
				}
				move_down_to(0);
				for(char ch : s) {
					assert(ch != '?');
				}
				// assert(false);
				printf("%s\n", s.c_str());
				exit(0);
			}
		}
	}
	puts("-1");
}

int main() {
	scanf("%d%d%d", &n, &m, &T);
	balancers.resize(m);
	for(pair<int,int>& p : balancers) {
		scanf("%d%d", &p.first, &p.second);
		--p.first;
		--p.second;
	}
	if(T == 1) {
		one();
	}
	else {
		two();
	}
}