（CodeForces - 771B）Bear and Different Names

In the army, it isn’t easy to form a group of soldiers that will be effective on the battlefield. The communication is crucial and thus no two soldiers should share a name (what would happen if they got an order that Bob is a scouter, if there are two Bobs?).

A group of soldiers is effective if and only if their names are different. For example, a group (John, Bob, Limak) would be effective, while groups (Gary, Bob, Gary) and (Alice, Alice) wouldn’t.

You are a spy in the enemy’s camp. You noticed n soldiers standing in a row, numbered 1 through n. The general wants to choose a group of k consecutive soldiers. For every k consecutive soldiers, the general wrote down whether they would be an effective group or not.

You managed to steal the general’s notes, with n - k + 1 strings s1, s2, …, sn - k + 1, each either “YES” or “NO”.

The string s1 describes a group of soldiers 1 through k (“YES” if the group is effective, and “NO” otherwise).

The string s2 describes a group of soldiers 2 through k + 1.

And so on, till the string sn - k + 1 that describes a group of soldiers n - k + 1 through n.

Your task is to find possible names of n soldiers. Names should match the stolen notes. Each name should be a string that consists of between 1 and 10 English letters, inclusive. The first letter should be uppercase, and all other letters should be lowercase. Names don’t have to be existing names — it’s allowed to print “Xyzzzdj” or “T” for example.

Find and print any solution. It can be proved that there always exists at least one solution.

Input

The first line of the input contains two integers n and k (2 ≤ k ≤ n ≤ 50) — the number of soldiers and the size of a group respectively.

The second line contains n - k + 1 strings s1, s2, …, sn - k + 1. The string si is “YES” if the group of soldiers i through i + k - 1 is effective, and “NO” otherwise.

Output

Find any solution satisfying all given conditions. In one line print n space-separated strings, denoting possible names of soldiers in the order. The first letter of each name should be uppercase, while the other letters should be lowercase. Each name should contain English letters only and has length from 1 to 10.

If there are multiple valid solutions, print any of them.

Examples

Input

8 3

NO NO YES YES YES NO

Output

Adam Bob Bob Cpqepqwer Limak Adam Bob Adam

Input

9 8

YES NO

Output

R Q Ccccccccc Ccocc Ccc So Strong Samples Ccc

Input

3 2

NO NO

Output

Na Na Na

題意：給你n個數，有一個小視窗長度為k，小視窗從1開始向右移動，如果輸入YES，則這個小視窗内的所有名字不能相同，否則名字可以相同。

思路：貪心，你會發現小視窗第一次停在左側為1的位置，并且前k-1個數各不相同，其實你輸出了k-1個數，剩下n-（k-1）的就是你輸入yes no的數量，因為他一共需要輸入n-k+1個yes或no。

先設定下輸出，如果num的值<91(Z的ascii碼為90) 輸出他就行，否則就輸出字元串A+（num+6）（因為a的ascii碼為97 不滿足條件num肯定>90,是以最小的值就是91+6=97了，避免輸出其他非字母字元） 你會問這樣可以嗎 你算下大寫的字元有26個 小寫的字母有26個 一共52個，題目給的資料為50個 剛剛好。

前k-1個數，先設定一個初始值num=65（A的ascii碼為65，轉化為字元串就是A了），然後num++直接輸出前k-1個

輸入一個YES，說明不能有重複的，是以跟前k-1個數一樣num++輸出。

輸入一個NO，讓這個值跟小視窗的第一個值相等，因為如果讓其他值跟他相等就不能保證下一次輸入YES，不一定是YES了，因為小視窗移動下一個，自然地就把上一步的第一個去除。 講到這裡就很明白了！！！！

AC代碼：

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
string getnum(ll num)
{
	string s;
	if(num<91)
		s.push_back(num);
	else
	{
		s.push_back('A');
		s.push_back(num+6);
	}
	return s;
}
int main()
{
	ll n,k;
	while(cin>>n>>k)
	{
		ll num=65;
		string s1[100],op;
		for(int i=0;i<n;i++)
		{
			if(i<k-1)
			{
				s1[i]=getnum(num);
				num++;
				cout<<s1[i]<<" ";
			}
			else
			{
				cin>>op;
				if(op=="YES")
				{
					s1[i]=getnum(num);
					num++;
					cout<<s1[i]<<" ";
				}
				else
				{
					s1[i]=s1[i-k+1];
					cout<<s1[i]<<" ";
				}
			}
		}
		cout<<endl;
	}
	return 0;
}