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;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
bitset<50001> B[50005];
int main() {
	int n, m, t;
	scanf("%d%d%d", &n, &m, &t);
	vector<int> x(m), y(m);
	for (int i = 0; i < m; ++i) scanf("%d%d", &x[i], &y[i]);
	if (t == 2) {
		if (n < 3) {
			printf("-1\n");
			return 0;
		}
		auto dir = [](int a, int b) {
			return a > b ? '^' : 'v';
		};
		vector<pair<char, int>> p;
		int a = 1, b = 2, c = 3;
		int ab = -1, ac = -1;
		for (int i = 0; i < m; ++i) {
			if (y[i] == a) swap(x[i], y[i]);
			if (x[i] == a && y[i] == b) {
				p.emplace_back(dir(a, b), ac); // b-c
				p.emplace_back(dir(b, a), ac); // a-c
				swap(a, c);
			} else if (x[i] == a && y[i] == c) {
				p.emplace_back(dir(c, a), ab); // a-b
				p.emplace_back(dir(a, c), ab); // c-b
				swap(a, b);
			} else {
				// a-b
				p.emplace_back((y[i] == a || y[i] == b) ? dir(x[i], y[i]) : dir(y[i], x[i]), ab);
				// a-c
				p.emplace_back((y[i] == a || y[i] == c) ? dir(x[i], y[i]) : dir(y[i], x[i]), ac);
			}
			ab = p.size() - 2;
			ac = p.size() - 1;
		}
		string ans;
		for (; ab != -1;) {
			ans += p[ab].first;
			ab = p[ab].second;
		}
		reverse(ans.begin(), ans.end());
		printf("%s\n", ans.c_str());
		return 0;
	}
	for (int i = 1; i <= n; ++i) B[i][i] = 1;
	for (int i = m - 1; i >= 0; --i) {
		B[x[i]] |= B[y[i]];
		B[y[i]] = B[x[i]];
	}
	auto sum = B[1];
	for (int i = 2; i <= n; ++i) {
		sum &= B[i];
	}
	int take = -1;
	for (int i = 1; i <= n; ++i) {
		if (sum[i] == 1) {
			take = i;
			break;
		}
	}
	if (take == -1) printf("-1\n");
	else {
		auto b = sum;
		b.reset();
		b[take] = 1;
		string ans;
		for (int i = m - 1; i >= 0; --i) {
			if (b[x[i]] == 1) {
				b[y[i]] = 1;
				ans += '^';
			} else if (b[y[i]] == 1) {
				b[x[i]] = 1;
				ans += 'v';
			} else {
				ans += '^';
			}
		}
		reverse(ans.begin(), ans.end());
		printf("%s\n", ans.c_str());
	}
}