#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7


							  //���C�u�����\��
							  //�l�b�g���[�N�t���[�F�a�{p188�`
class NetworkFlow {
public:
	//�����F���_��
	NetworkFlow(int size) {
		G.resize(size);
		used.resize(size);
	}

	//from����to�֌������e��cap�̕ӂ��O���t�ɒǉ�����
	void add_edge(int from, int to, int cap) {
		Edge e1 = { to, cap, (int)G[to].size() };
		Edge e2 = { from, 0, (int)G[from].size() - 1 };
		G[from].push_back(e1);
		G[to].push_back(e2);
	}

	//s����t�ւ̍ő嗬�����߂�
	int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			fill(used.begin(), used.end(), false);
			int f = dfs(s, t, INF);
			if (f == 0)return flow;
			flow += f;
		}
	}


private:
	//�^�ƕϐ�
	struct Edge { int to, cap, rev; };//�ӂ�\���\���́i�s����A�e�ʁA�t�Ӂj
	vector<vector<Edge>> G;   //�O���t�̗אڃ��X�g�\��
	vector<bool> used;//DFS�Ŋ��ɒ��ׂ����̃t���O

					  //�֐�
					  //�����p�X��DFS�ŒT��
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		used[v] = true;
		REP(i, (int)G[v].size()) {
			Edge& e = G[v][i];
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
};
using NF = NetworkFlow;

//�ϐ�
constexpr int ALNUM = 26;
int N;
vector<vector<int>> s(ALNUM, vector<int>(ALNUM, 0));
vector<bool> res(ALNUM, false);





//�T�u�֐�
//����
void input()
{
	cin >> N;
	REP(i, N) {
		string ts;
		cin >> ts;
		int from = ts.front() - 'a';
		int to = ts.back() - 'a';
		s[from][to]++;
	}
}


//�v�Z
void calc()
{
	REP(k, ALNUM) {
		int inAll = 0;
		int outAll = 0;
		REP(i, ALNUM) {
			//if (i == k)continue;
			outAll += s[k][i];
			inAll += s[i][k];
		}
		NetworkFlow nf(ALNUM + 1);
		REP(i, ALNUM)REP(j, ALNUM) {
			//if (i == j)continue;
			nf.add_edge(i, (j == k ? ALNUM : j), s[i][j]);
		}
		int roop = nf.max_flow(k, ALNUM);
		
		if (inAll != 0 && inAll >= outAll && outAll == roop)res[k] = true;
		//char t = 'a' + k;
		//string tmp;
		//tmp += t;
		//cout << tmp << " " << inAll << " " << roop << " " << outAll << endl;
		//cout << (in < out) << endl;
		//if (in > out)res[k] = true;
	}
}


//�o��
void output()
{
	REP(i, ALNUM)if (res[i]) {
		char t = 'a' + i;
		string tmp;
		tmp += t;
		cout << t << endl;
	}
}


//�f�o�b�O
void debug()
{
	int N;
	cin>>N;
}


//���C���֐�
int main()
{
	input();
	calc();
	output();
	//debug();
	
	return 0;
}


### Prompt

Please provide a Cpp coded solution to the problem described below:

Problem

Here is a list of strings. Let's take a break and play with shiritori. Shiritori is performed according to the following rules.

1. First of all, select one of your favorite strings from the list and exclude that string from the list.
2. Next, select one character string from the list in which the last character of the previously selected character string is the first character.
3. Exclude the selected string from the list.



After this, steps 2 and 3 will be repeated alternately.

Now, let's assume that this shiritori is continued until there are no more strings to select from the list in 2. At this time, I want to list all the characters that can be the "last character" of the last selected character string.

Constraints

The input satisfies the following conditions.

* $ 1 \ le N \ lt 10 ^ 4 $
* $ 1 \ le | s_i | \ lt 100 $
* $ s_i \ neq s_j (i \ neq j) $
* The string contains only lowercase letters

Input


$ N $
$ s_1 $
$ s_2 $
$ s_3 $
::
$ s_N $


The number of strings $ N $ is given on the first line.
The following $ N $ line is given a list of strings.

Output

Output the characters that can be the "last character" of the last selected character string in ascending order from a to z in lexicographical order.

Examples

Input

5
you
ate
my
hum
toast


Output

e
t
u


Input

7
she
sells
sea
shells
by
the
seashore


Output

a
e
y

### Response

```cpp
#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7


							  //���C�u�����\��
							  //�l�b�g���[�N�t���[�F�a�{p188�`
class NetworkFlow {
public:
	//�����F���_��
	NetworkFlow(int size) {
		G.resize(size);
		used.resize(size);
	}

	//from����to�֌������e��cap�̕ӂ��O���t�ɒǉ�����
	void add_edge(int from, int to, int cap) {
		Edge e1 = { to, cap, (int)G[to].size() };
		Edge e2 = { from, 0, (int)G[from].size() - 1 };
		G[from].push_back(e1);
		G[to].push_back(e2);
	}

	//s����t�ւ̍ő嗬�����߂�
	int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			fill(used.begin(), used.end(), false);
			int f = dfs(s, t, INF);
			if (f == 0)return flow;
			flow += f;
		}
	}


private:
	//�^�ƕϐ�
	struct Edge { int to, cap, rev; };//�ӂ�\���\���́i�s����A�e�ʁA�t�Ӂj
	vector<vector<Edge>> G;   //�O���t�̗אڃ��X�g�\��
	vector<bool> used;//DFS�Ŋ��ɒ��ׂ����̃t���O

					  //�֐�
					  //�����p�X��DFS�ŒT��
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		used[v] = true;
		REP(i, (int)G[v].size()) {
			Edge& e = G[v][i];
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
};
using NF = NetworkFlow;

//�ϐ�
constexpr int ALNUM = 26;
int N;
vector<vector<int>> s(ALNUM, vector<int>(ALNUM, 0));
vector<bool> res(ALNUM, false);





//�T�u�֐�
//����
void input()
{
	cin >> N;
	REP(i, N) {
		string ts;
		cin >> ts;
		int from = ts.front() - 'a';
		int to = ts.back() - 'a';
		s[from][to]++;
	}
}


//�v�Z
void calc()
{
	REP(k, ALNUM) {
		int inAll = 0;
		int outAll = 0;
		REP(i, ALNUM) {
			//if (i == k)continue;
			outAll += s[k][i];
			inAll += s[i][k];
		}
		NetworkFlow nf(ALNUM + 1);
		REP(i, ALNUM)REP(j, ALNUM) {
			//if (i == j)continue;
			nf.add_edge(i, (j == k ? ALNUM : j), s[i][j]);
		}
		int roop = nf.max_flow(k, ALNUM);
		
		if (inAll != 0 && inAll >= outAll && outAll == roop)res[k] = true;
		//char t = 'a' + k;
		//string tmp;
		//tmp += t;
		//cout << tmp << " " << inAll << " " << roop << " " << outAll << endl;
		//cout << (in < out) << endl;
		//if (in > out)res[k] = true;
	}
}


//�o��
void output()
{
	REP(i, ALNUM)if (res[i]) {
		char t = 'a' + i;
		string tmp;
		tmp += t;
		cout << t << endl;
	}
}


//�f�o�b�O
void debug()
{
	int N;
	cin>>N;
}


//���C���֐�
int main()
{
	input();
	calc();
	output();
	//debug();
	
	return 0;
}


```