1.4.1 many, many symbols (cin/cout unbinding, O3 optimization)

1.4.1 Many, many talismans

Description

The world of clouds is a world with Taoism , The world has all kinds of magic .

Once there was a great sage , Compiled all kinds of immortals into 《 Daofa 3000 》 In the book , And give each method a number . Although the title of the book is called 《 Daofa 3000 》, But the actual number of Daoism is far more than 3000 , This book is now widely popular in the cloud world , therefore , All major sects use the Daoism number in this book to identify Daoism .

Xiao Yun is a family of practice , However, the talent is extremely poor , It's difficult to practice Taoism . Fortunately, Xiao Yun has a large number of Taoist symbols given by his family , Using Taoist symbols can directly use Taoist methods .

Each Taoist symbol has a Taoist number , It represents the Tao method that this Taoist symbol can be used directly .

Xiao Yun has qqq Such as “ bib_ibi​ Can I use Taoism ” The problem of . Because Xiao Yun has too many Taoist symbols and questions , therefore , It needs magical you to help him .

Input

The first line is an integer n n n . Indicates the number of Taoist symbols .

The second line n n n Integers separated by spaces , The first i The number means ai a_i ai​ . The meaning is shown in the title description .

The third line is a positive integer q q q . Indicates the number of questions of Xiaoyun .

In the fourth row q q q Positive integers separated by spaces , The first i The number means   bi b_i bi​  . The meaning is shown in the title description .

Output

Output only one line , For a length of nnn String s. When Xiao Yun can use the debut method bib_ibi​ Time output si=s_i=si​='Y', otherwise si=s_i=si​= ‘N’.

Sample Input 1

10
5 5 6 8 8 9 12 23 41 79
15
50 8 9 23 233 5 6 8 79 12 5 8 9 41 22

Sample Output 1

NYYYNYYYYYYYYYN

Hint

Data range ：

50% Data are available. ：1≤n,q≤5000

100% Data are available. ：1≤n,q≤106

1≤ai​,bi​≤ 2^31−1

unordered_map<string,int> ump There are three groups of tests that can't pass ,unordered_map<int,int> ump can AC, Is it scanf Than cin fast , Or why .

Now it's clear , It should be scanf Than cin fast . But we can also be right cin/cout To optimize , You need to write these two sentences in the function ：

std::ios::sync_with_stdio(false);// With these two sentences, you can't use printf,scanf
std::cin.tie(0);

Add... Before the main function O3 Optimize , Will be a step faster , Especially for STL More obvious for containers , Although it has not been verified , But write it down first .
#pragma GCC optimize(3)

/** //  Three test points cannot pass 
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <string>
using namespace std;

int main()
{
    int n,p;
    scanf("%d",&n);
    unordered_map<string,int> ump;
    string str;
    for(int i=0;i<n;++i)
    {
        cin >> str;
        ump[str]=1;
    }
    scanf("%d",&p);
    for(int i=0;i<p;++i)
    {
        cin >> str;
        if(ump[str]==1)
            printf("Y");
        else
            printf("N");

    }
    return 0;
}
*/

// can AC
/**
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <string>
using namespace std;

int main()
{
    int n,p;
    scanf("%d",&n);
    unordered_map<int,int> ump;
    int val;
    for(int i=0;i<n;++i)
    {
        scanf("%d",&val);
        ump[val]=1;
    }
    scanf("%d",&p);
    for(int i=0;i<p;++i)
    {
        scanf("%d",&val);
        if(ump[val]==1)
            printf("Y");
        else
            printf("N");
    }
    return 0;
}

*/

// The answer to the question 
#include <stdio.h>
#include <string>
using namespace std;
int a[1001000];
int n,q,b;
string S;
// Direct dichotomy 
int find(int x)
{
    int mid,l=1,r=n;
  while(l<=r)
  {
    mid=(l+r)/2;
 	if(a[mid]>x)			//objective1  How to dichotomy ？( If you really give the prompt again, it will be directly the code QWQ --Megumin)
       r=mid-1;
    else if(a[mid]<x)
      l=mid+1;
    else
      return mid;
  }
    return -1;// Not found
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    scanf("%d",&q);
    for(int i = 1;i <= q;i ++){
        scanf("%d",&b);
        if(find(b) != -1)
            S += 'Y';
        else
            S += 'N';
    }
    printf("%s\n",S.c_str());
}

/**
    4)// Yes cin/cout Unbound , Improve cin/cout The speed of ;
     can AC;
*/

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

#pragma GCC optimize(3)
int main()
{
    std::ios::sync_with_stdio(false);// With these two sentences, you can't use printf,scanf
    std::cin.tie(0);
    int n,p;
    cin >> n;
    unordered_map<string,int> ump;
    string str;
    for(int i=0;i<n;++i)
    {
        cin >> str;
        ump[str]=1;
    }

    cin >> p;
    for(int i=0;i<p;++i)
    {
        cin >> str;
        if(ump[str]==1)
            cout << 'Y';
        else
            cout << 'N';
    }
    return 0;
}