You are given two strings s and t consisting of lowercase English letters and an integer L.

We will consider generating a string of length L by concatenating one or more copies of s and t. Here, it is allowed to use the same string more than once.

For example, when s = `at`, t = `code` and L = 6, the strings `atatat`, `atcode` and `codeat` can be generated.

Among the strings that can be generated in this way, find the lexicographically smallest one. In the cases given as input, it is always possible to generate a string of length L.

Constraints

* 1 ≤ L ≤ 2 × 10^5
* 1 ≤ |s|, |t| ≤ L
* s and t consist of lowercase English letters.
* It is possible to generate a string of length L in the way described in Problem Statement.

Input

Input is given from Standard Input in the following format:


N
x_1 s_1
x_2 s_2
:
x_N s_N


Output

Print the lexicographically smallest string among the ones that can be generated in the way described in Problem Statement.

Examples

Input

6
at
code


Output

atatat


Input

8
coding
festival


Output

festival


Input

8
same
same


Output

samesame


Input

10
coin
age


Output

ageagecoin
#include <string>
#include <iostream>
using namespace std;
int L; string s, t;
int main() {
	cin >> L >> s >> t;
	if (s > t) swap(s, t);
	if (t.substr(0, s.size()) != s) {
		if (s > t) swap(s, t);
	}
	else {
		string ca = s, cb = t;
		while (ca.size() < 10000000) ca += s;
		while (cb.size() < 10000000) cb += s;
		if (ca > cb) swap(s, t);
	}
	int b = 0, bb = 0;
	for (int i = 0; i <= L; i += s.size()) {
		if ((L - i) % t.size() == 0) {
			b = i / s.size();
			bb = (L - i) / t.size();
		}
	}
	for (int i = 0; i < b; i++) cout << s;
	for (int i = 0; i < bb; i++) cout << t;
	cout << endl;
	return 0;
}