#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
struct trie{
trie *ch[26];
trie(){
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root[2];
void add(string &s, int k){
trie *now=&root[k];
for(int i=0; i<(int)s.size(); i++){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
}
bool dfs(trie *a, trie *b, int k){
bool ans;
if(k&1){
ans=0;
for(int i=0; i<26; i++){
if(a->ch[i] && b->ch[i]) ans|=dfs(a->ch[i], b->ch[i], k+1);
else if(a->ch[i]){
ans=1;
break;
}
}
}
else{
ans=1;
for(int i=0; i<26; i++){
if(a->ch[i] && b->ch[i]) ans&=dfs(a->ch[i], b->ch[i], k+1);
else if(b->ch[i]){
ans=0;
break;
}
}
}
return ans;
}
int main(){
fast();
int n; cin>>n;
for(int i=1; i<=n; i++){
string s; cin>>s; add(s, 0);
}
int m; cin>>m;
for(int i=1; i<=m; i++){
string s; cin>>s; add(s, 1);
}
if(dfs(&root[0], &root[1], 1)) cout<<"Nina";
else cout<<"Emilija";
}
/*
struct trie{
bool val;
trie *ch[26];
trie(){
val=0;
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root;
void add(string &s){
trie *now=&root;
for(int i=0; i<(int)s.size(); i++){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
now->val=1;
}
int main(){
fast();
int n, m; cin>>n>>m;
string s; cin>>s;
for(int i=1; i<=m; i++){
string t; cin>>t; add(t);
}
string t="";
int ans=0;
trie *now=&root;
for(int i=0; i<n; i++){
if(!now->ch[s[i]-'a']){
t.clear();
now=&root;
}
if(now->ch[s[i]-'a']){
now=now->ch[s[i]-'a'];
if(now->val){
ans++;
t.clear();
now=&root;
}
else t+=s[i];
}
}
cout<<ans;
}
*/
/*
#define int long long
const int N=5e3, NN=1e6, mod=1e9+7;
int dp[N+1];
struct trie{
bool val;
trie *ch[26];
trie(){
val=0;
for(int i=0; i<26; i++) ch[i]=NULL;
}
}root;
void add(string &s){
trie *now=&root;
for(int i=(int)s.size()-1; i>=0; i--){
if(!now->ch[s[i]-'a']) now->ch[s[i]-'a']=new trie();
now=now->ch[s[i]-'a'];
}
now->val=1;
}
vector<int> v;
void f(string &s){
trie *now=&root;
for(int i=(int)s.size()-1; i>=0; i--){
int c=s[i]-'a';
if(!now->ch[c]) return;
now=now->ch[c];
if(now->val) v.push_back(i);
}
}
// int now=1, trie[NN+1][26], exi[NN+1], word[NN+1];
// void add(string &s){
// int id=0;
// for(int i=s.size()-1; i>=0; i--){
// if(!exi[trie[id][s[i]-'a']]){
// trie[id][s[i]-'a']=now++;
// exi[now-1]=1;
// }
// id=trie[id][s[i]-'a'];
// }
// word[id]=1;
// }
// vector<int> v;
// void f(string &s){
// int id=0;
// for(int i=s.size()-1; i>=0; i--){
// if(!exi[trie[id][s[i]-'a']]) return;
// id=trie[id][s[i]-'a'];
// if(word[id]) v.push_back(i);
// }
// }
signed main(){
fast();
string s; cin>>s;
int n=(int)s.size(), k; cin>>k;
for(int i=1; i<=k; i++){
string t; cin>>t; add(t);
}
string t="";
dp[0]=1;
for(int i=1; i<=n; i++){
t+=s[i-1];
v.clear();
f(t);
for(auto j:v) dp[i]+=dp[j];
dp[i]%=mod;
}
cout<<dp[n];
//for(int i=0; i<=n; i++) cout<<dp[i]<<' ';
}
*/
//Trie
/*
const int LOG=30;
struct trie {
int val;
trie *ch[2]; // [26]
trie() {
val = 0;
ch[0] = NULL;
ch[1] = NULL;
}
} root;
void add(int x) {
trie *now = &root;
now->val++;
for (int i=LOG-1;i>=0;i--) {
if (!now->ch[(x>>i)&1]) {
now->ch[(x>>i)&1] = new trie();
}
now = now->ch[(x>>i)&1];
now->val++;
}
}
int main() {
int a = 5, b = 7;
int *c, *d;
c = &a;
cout << *c << endl;
a = 3;
cout << *c << endl;
*c = 6;
cout << a << endl;
d = c;
(*d)++;
cout << *c << endl;
c = &b;
*c = 4;
cout << *d << endl;
(*d).val
d->val
*d.val
return 0;
}
*/
/*
vector<int> manacher(string s){
int n=s.size(), l=0, r=0;
vector<int> c(n+2);
s='^'+s+'#';
for(int i=1; i<=n; i++){
if(i<r) c[i]=min(r-i, c[l+r-i]);
while(s[i-c[i]]==s[i+c[i]]) c[i]++;
if(i+c[i]>r){
l=i-c[i], r=i+c[i];
}
}
return c;
}
string solve(string s){
int n=s.size();
int l=0, r=n-1;
while(l<r && s[l]==s[r]) l++, r--;
if(r<=l) return s;
l--, r++;
string news="";
for(int i=0; i<n; i++) news+=string("#")+s[i];
news+='#';
auto c=manacher(news);
int ans=0, idx=0, m=news.size(), cek;
for(int i=1; i<=m; i++){
int ki=(i-c[i]+2)/2-1, ka=(i+c[i]-2)/2-1;
if(ki-1<=l && ka+1<r){
int ov=l+1-(l-(ki-1));
if(c[i]-1+2*ov>ans){
ans=c[i]-1+2*ov;
idx=i;
cek=0;
}
}
else if(ka+1>=r && ki-1>l){
int ov=l+1-(ka+1-r);
if(c[i]-1+2*ov>ans){
ans=c[i]-1+2*ov;
idx=i;
cek=1;
}
}
//cout<<news[i-1]<<' '<<c[i]<<'\n';
}
// cout<<ans<<' '<<idx<<'\n';
int ki=(idx-c[idx]+2)/2-1, ka=(idx+c[idx]-2)/2-1;
string t="";
if(!cek){
int ov=(l-(ki-1));
t+=s.substr(0, l+1-ov+c[idx]-1);
if(r+ov<n) t+=s.substr(r+ov, l+1-ov);
}
else{
int ov=(ka+1-r);
if(l-ov>=0) t+=s.substr(0, l+1-ov);
t+=s.substr(ki, (l+1-ov)+c[idx]-1);
}
return t;
}
int main(){
fast();
int teskes; cin>>teskes;
while(teskes--){
string s; cin>>s;
string x=solve(s);
reverse(s.begin(), s.end());
string y=solve(s);
if(x.size()>=y.size()) cout<<x;
else cout<<y;
cout<<'\n';
}
}
*/
/*
vector<int> manacher(string s){
int n=s.size(), l=0, r=0;
vector<int> c(n+2);
s='^'+s+'#';
for(int i=1; i<=n; i++){
if(i<r) c[i]=min(r-i, c[l+r-i]);
while(s[i-c[i]]==s[i+c[i]]) c[i]++;
if(i+c[i]>r){
l=i-c[i], r=i+c[i];
}
}
return c;
}
void solve(string s){
int n=s.size();
string news="";
for(int i=0; i<n; i++) news+=string("#")+s[i];
news+='#';
auto c=manacher(news);
int ans=0, idx=0, m=news.size();
for(int i=1; i<=m; i++){
if(c[i]-1>ans){
ans=c[i]-1;
idx=(i-c[i]+2)/2-1;
}
}
cout<<s.substr(idx, ans);
}
int main(){
fast();
string s; cin>>s;
solve(s);
}
*/
//Manacher's Algo
/*
vector<int> manacher_odd(string s){
int n=s.size(), l=0, r=0;
s='^'+s+'#';
vector<int> c(n+2);
for(int i=1; i<=n; i++){
if(i<r) c[i]=min(r-i, c[l+(r-i)]);
while(s[i-c[i]]==s[i+c[i]]) c[i]++;
if(i+c[i]>r){
l=i, r=i+c[i];
}
}
return c;
}
vector<int> manacher_even(string s){
int n=s.size();
string news="";
for(int i=0; i<n; i++){
news+=string("#")+s[i];
}
return manacher_odd(news+'#');
}
int main(){
fast();
string s; cin>>s;
auto co=manacher_odd(s), ce=manacher_even(s);
}
*/
/*
int main(){
fast();
string s; cin>>s;
int n=s.size(), l=0, r=0;
int obelix=0, suff=0;
vector<int> z(n);
for(int i=1; i<n; i++){
if(i<r) z[i]=min(r-i, z[i-l]);
while(z[i]+i<n && s[z[i]]==s[z[i]+i]) z[i]++;
if(i+z[i]>r){
l=i, r=i+z[i];
}
obelix=max(obelix, z[i]-(z[i]+i==n));
if(z[i]+i==n && z[i]<=obelix) suff=max(suff, z[i]);
}
if(suff) cout<<s.substr(0, suff);
else cout<<"Just a legend";
}
*/
//Z-Algo
/*
vector<int> z_f(string &s){
int n=s.size(), l=0, r=0;
vector<int> z(n);
for(int i=1; i<n; i++){
if(i<r){
z[i]=min(r-i, z[i-l]);
}
while(z[i]+i<n && s[z[i]]==s[z[i]+i]) z[i]++;
if(i+z[i]>r){
l=i, r=i+z[i];
}
cout<<z[i]<<' ';
}
cout<<'\n';
return z;
}
int main(){
string s; cin>>s;
auto z=z_f(s);
//for(auto &i:z) cout<<i<<' ';
}
*/
/*
const int N=6000;
int a[N+5], b[N+1];
void f(string &s, int *c){
int j=0;
for(int i=1; i<s.size(); i++){
while(j && s[i]!=s[j]) j=c[j-1];
if(s[i]==s[j]) j++;
c[i]=j;
}
}
tuple<int,int,int> solve(string &s, string &t, bool rev){
int n=s.size(), m=t.size();
tuple<int,int,int> ans={0, 0, 0};
string t2=t;
reverse(t2.begin(), t2.end());
for(int i=0; i<n; i++){
string s1=s.substr(0, i), s2=s.substr(i, n-i);
reverse(s1.begin(), s1.end());
s1+='#'+t, s2+='#'+t2;
f(s1, a); f(s2, b);
for(int j=1; j<=m; j++){
ans=max(ans, {a[i+j]+b[n+m-i-j], i-a[i+j], rev? m-j-b[n+m-i-j] : j-a[i+j]});
}
}
return ans;
}
int main(){
fast();
string s, t; cin>>s>>t;
auto ans=solve(s, t, 0);
reverse(t.begin(), t.end());
ans=max(ans, solve(s, t, 1));
cout<<get<0>(ans)<<'\n'<<get<1>(ans)<<' '<<get<2>(ans);
}
*/
/*
vector<int> f1(string &s, string &t){
int n=s.size(), m=t.size(), j=0;
vector<int> a(n), b(m);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=a[j-1];
if(s[i]==s[j]) j++;
a[i]=j;
}
j=0;
for(int i=0; i<m; i++){
while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
if(s[j]==t[i]) j++;
b[i]=j;
}
return b;
}
vector<int> f2(string &s, string &t){
int n=s.size(), m=t.size(), j=0;
vector<int> a(n), b(m);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=a[j-1];
if(s[i]==s[j]) j++;
a[i]=j;
}
j=0;
for(int i=m-1; i>=0; i--){
while(j==n || (j>0 && s[j]!=t[i])) j=a[j-1];
if(s[j]==t[i]) j++;
b[i]=j;
}
return b;
}
int main(){
fast();
string s, t1, t2; cin>>s>>t1;
t2=t1; reverse(t2.begin(), t2.end());
int n=s.size(), m=t1.size();
int ki=1, ka=n, ans, j1, j2;
while(ki<=ka){
int k=(ki+ka)/2;
bool cek=false;
for(int l=0; l+k-1<n; l++){
if(cek) break;
if(k>m){
cek=true;
break;
}
string s1=s.substr(l, k);
string s2=s1; reverse(s2.begin(), s2.end());
auto val1=f1(s1, t1), val2=f2(s2, t1), val3=f1(s1, t2), val4=f2(s2, t2);
for(int i=0; i+k-1<m; i++){
if(val1[i+k-1]+val2[i]>=k){
ans=k, j1=l, j2=i;
cek=true;
break;
}
}
for(int i=0; i+k-1<m; i++){
if(val3[i+k-1]+val4[i]>=k){
ans=k, j1=l, j2=m-(i+k-1)-1;
cek=true;
break;
}
}
// if(ans==k){
// cout<<s1<<'\n';
// for(int i=0; i<m; i++) cout<<val3[i]<<' ';
// cout<<'\n';
// for(int i=0; i<m; i++) cout<<val4[i]<<' ';
// cout<<'\n';
// }
}
if(cek) ki=k+1;
else ka=k-1;
}
cout<<ans<<'\n';
cout<<j1<<' '<<j2;
}
*/
//KMP
/*
vector<int> f(string &s){
int n=s.size(), j=0;
vector<int> v(n);
for(int i=1; i<n; i++){
while(j>0 && s[i]!=s[j]) j=v[j-1];
if(s[i]==s[j]) j++;
v[i]=j;
}
return v;
}
int main(){
fast();
string s, t; cin>>s>>t;
string temp=t+'0'+s;
auto lps=f(temp);
int ans=0;
for(auto i:lps) ans+=(i==t.size());
cout<<ans;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
716 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
452 KB |
Output is correct |
| 4 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
21212 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19800 KB |
Output is correct |
| 3 |
Correct |
12 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
16 ms |
20572 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
21592 KB |
Output is correct |
| 2 |
Correct |
13 ms |
22620 KB |
Output is correct |
| 3 |
Correct |
13 ms |
20860 KB |
Output is correct |
| 4 |
Correct |
12 ms |
21336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
20316 KB |
Output is correct |
| 2 |
Correct |
13 ms |
20056 KB |
Output is correct |
| 3 |
Correct |
13 ms |
20568 KB |
Output is correct |
| 4 |
Correct |
14 ms |
21852 KB |
Output is correct |
