#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int op,p,ps,pd,a[100001],i,n,y,x,m;
int cautare_bin(int x){ //cautare binara pe biti !!! returneaza
int i,pas=1; // poz elementului x daca exista in sir
while(pas*2<=n)pas=pas*2; //sau poz elementului mai mic
for(i=1;pas;pas=pas/2) //ca x daca x nu exista in sir
if(i+pas<=n and a[i+pas]<=x)i+=pas;
return i;
}
int cautare_bin1(int x){//returneaza poz elementului x daca exista in sir
int st,dr,k,mid; //sau poz elementului mai mare ca x daca x nu exista in sir
st=1; dr=n; k=0;
while(st<=dr){
mid=(st+dr)/2;
if(a[mid]==x)return mid;
if (a[mid]>x) dr=mid-1;
else st=mid+1;
}
return dr;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)f>>a[i];
f>>m;
for(i=1;i<=m;i++){
f>>op>>y;
p=cautare_bin(y);
pd=p;ps=p;
if(a[p]==y){
while(a[pd]==y)pd++;
while(a[ps]==y)ps--;
if(op==0) g<<--pd<<'\n';
if(op==1) g<<--pd<<'\n';
if(op==2) g<<++ps<<'\n';
}
if(a[p]!=y){
if(op==0) g<<-1<<'\n';
if(op==1)if(y>a[p]) g<<p<<'\n';else g<<--p<<'\n';
if(op==2) if(y>a[p]) g<<p+1<<'\n';else g<<p<<'\n';
}
}
f.close();g.close();
return 0;
}
//#include <iostream>
//using namespace std;
//int i,n,a[1003],ok;
//int oarecare;
//int main()
//{
// cin>>n;oarecare=1;
// for(i=1; i<=n; i++)cin>>a[i];
// ok=1;//constant
// for(i=1; i<n; i++)
// if(a[i]!=a[i+1])ok=0;
// if(ok==1){cout<<"sir constant";oarecare=0;}
// else
// {
// ok=1;//strict cresc
// for(i=1; i<n; i++)
// if(a[i]>=a[i+1])ok=0;
// if(ok==1){cout<<"sir strict crescator";;oarecare=0;}
// else
// {
// ok=1;//cresc
// for(i=1; i<n; i++)
// if(a[i]>a[i+1])ok=0;
// if(ok==1){cout<<"sir crescator";oarecare=0;}
// }
// ok=1;// strict desc
// for(i=1; i<n; i++)
// if(a[i]<=a[i+1])ok=0;
// if(ok==1){cout<<"sir strict descrescator";oarecare=0;}
// else
// {
// ok=1;//desc
// for(i=1; i<n; i++)
// if(a[i]<a[i+1])ok=0;
// if(ok==1){cout<<"sir descrescator";;oarecare=0;}
// }
// }
// if(oarecare==1)cout<<"sir neordonat";
// return 0;
//}
//#include <iostream>
//using namespace std;
//int i,n,p,x,sol=-1,r,ere;
//int main()
//{
//cin>>n;
//p=1;
//for(i=1;i<=n;i++){
// cin>>x;
// if(x%2==0)sol=x;
//}
//if(sol==-1)cout<<"imposibil";
//else cout<<sol;
//return 0;
//}
//#include<fstream>//
//using namespace std;
//ifstream f("pachete.in");
//ofstream g("pachete.out");
//int x,gol,a[100003],j,k,p,i,n,b[2][400004];
//int main(){
//f>>n;
//for(i=1;i<=n;i++)f>>a[i];
//gol=n+1;
// for(i=1;i<=n;i++)
// if(a[i]!=i){
// x=a[i];
// a[gol]=a[x];
// k++;b[0][k]=x;b[1][k]=gol;
// a[x]=a[i];
// k++;b[0][k]=i;b[1][k]=x;
// gol=i;
// g<<gol<<" ";
// }
// g<<k<<endl;
// for(i=1;i<=k;i++)
// g<< b[0][i]<<" "<<b[1][i]<<endl;
//return 0;
//}
//#include <cstdio>
//
//using namespace std;
//
//int n, a[3][100001], k, x, i, li, ls, ga,m,kk;
//int main()
//{
// freopen("schi1.in", "r" ,stdin);
// freopen("schi1.out", "w" ,stdout);
// //scanf("%d", &n);
// //printf("%d",n);
// scanf("%d", &n); k = 0;
// for(i = 1; i <= n; i++)
// {
// //f >> x;
// scanf("%d", &x);
// if(x > a[1][k])
// { k++;
// a[1][k] = x;
// a[2][k] = 1;
// }
// else
// { if(k == 0)k++;
// a[2][k]++;
// }
// }
// m=k;
// // f >> kk;
// scanf("%d", &kk);
// for(i=1;i<=kk;i++) {
//
//scanf("%d", &x);
// li = 1; ls = m; ga = 0;
// while(li <= ls and ga == 0)
// {
// k = (li + ls) / 2;
// if(a[1][k] == x) ga = 1;
// else
// if(x < a[1][k]) ls = k - 1;
// else li = k + 1;
// }
// if (ga == 1) printf("%d",a[2][k], "%c");
// else printf("%d",0, "%c");
// }
// return 0;
//}
//#include<iostream>//
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(){
//int j;
//for(j=1;j<=n;j++)g<<a[j];
//g<<endl;
//}
//int cont( int k){
//if(k>n)return 0; //{verificarea conditiilor de validare}
//return 1;
//}
//int sol(int k){
// int k1=0,k2=0,k3=0;
// if(k!=n+1)return 0;
// for(i=1;i<=n;i++)
// {if(a[i]==1)k1++;
// if(a[i]==2)k2++;
// if(a[i]==3)k3++;
// }
// if(k1!=1 or k2!=2 or k3!=3)return 0;
// return 1;
//}
//void bt(int k){
// int i;
// if(sol(k))afiseaza();
// else
// for(i=1;i<=3;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
//
////9
////1 11
////4 6
////1 5
////3 8
////9 10
////8 12
////10 13
////5 10
////4 7
//#include<fstream>//spectacole
//using namespace std;
//ifstream fi("spect.in");
//ofstream fo("spect.out");
//;struct interval{
// int st,dr;
//}a[100];
//int n,i,j,sf;
//bool ord;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// fi>>a[i].st>>a[i].dr;
// ord=false; //bubble sort
// while(ord==false){
// ord=true;
// for(i=1;i<n;i++)
// if(a[i].dr>a[i+1].dr)
// {swap(a[i],a[i+1]);ord=false;}
// }
////sort(a+1,a+n+1);
// fo<<a[1].st<<" "<<a[1].dr<<endl;sf=a[1].dr;
// for(i=2;i<=n;i++)
// if(a[i].st>=sf){
// fo<<a[i].st<<" " <<a[i].dr<<endl;
// sf=a[i].dr;
// }
// return 0;
//}
//#include<iostream>//scara cu pasul 1, 2, 3
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int n;
//int i_prim(int n){
//int a,b,d,prim=0;
//a=n;
//while(prim==0){
// prim=1;
// for(d=2;d*d<=a;d++)
// if(a%d==0){prim=0;break;}
// a++;
//}
//prim=0;
//b=n;
//while(prim==0){
// prim=1;
// for(d=2;d*d<=b;d++)
// if(b%d==0){prim=0;break;}
// b--;
//}
//a--;b++;
//return a-b;
//}
//string fii;
//int main(){
// fii='a'+'b';
// cout<<fii;
// cin>>n;
// cout<<i_prim(n);
//}
//#include<iostream>//scara cu pasul 1, 2, 3
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,k1,k2,k3,b[11],sol[10],i,kk,j,mini=100;
//void afiseaza(int k){
//int j,kal;
//for(j=1;j<k;j++)g<<a[j]<<" ";g<<endl;
//kal=0;
//for(j=1;j<k;j++)
// { if(a[j]==1)kal+=k1;
// if(a[j]==2)kal+=k2;
// if(a[j]==3)kal+=k3;
// }
// if(mini>kal){mini=kal;kk=k-1;for(j=1;j<k;j++)sol[j]=a[j];}
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(k>n)return 0;
//return 1;
//}
//int solutie(int k){
//int s=0;
//for(i=1;i<=k-1;i++)
// s+=a[i];
//if(s!=n) return 0;
//return 1;
//}
//void bt(int k){
// int i;
// if(solutie(k))afiseaza(k);
// else
// for(i=1;i<=3;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n>>k1>>k2>>k3;
// bt(1);
// g<<endl;
// for(i=1;i<=kk;i++)g<<sol[i]<<" ";
//}
////toate numerele de n cifre diviz. cu 13
//#include<iostream>//
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(){
//int j;
//for(j=1;j<=n;j++)g<<a[j];
//g<<endl;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(k>n)return 0;
//if(k>1)
// if(a[k]-a[k-1]==1 or a[k]-a[k-1]==-1)return 0;
//if(a[1]==0)return 0;
//return 1;
//}
//int sol(int k){
// int x=0;
// if(k!=n+1)return 0;
// for(int j=1;j<=n;j++)
// x=x*10+a[j];
// if(x%13!=0)return 0;
// return 1;
//}
//void bt(int k){
// int i;
// if(sol(k))afiseaza();
// else
// for(i=0;i<=9;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
////suma s scrisa ca suma de numere dintr-un sir
////(solutia minima ca lungime )
////5 10
////2 8 2 6 4 => 6 4
//#include<fstream>
//#include<iostream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11],s,i,j,mini=100,sol[11];
//void afiseaza(int n){
//int k=0,j,sum=0;
//for(j=1;j<=n;j++)
// if(a[j]==1)sum+=b[j];
//if(sum==s){
// for(j=1;j<=n;j++)
// if(a[j]==1)k++;
// if(mini>k){mini=k;for(j=1;j<=n;j++)sol[j]=a[j];}
//}
//}
//
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//return 1;
//}
//void bt(int k){
// int i;
// if(k==n+1)afiseaza(k-1);
// else
// for(i=0;i<=1;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n>>s;
// for(i=1;i<=n;i++)f>>b[i];
// bt(1);
// for(j=1;j<=n;j++)
// if(sol[j]==1)g<<b[j]<<" ";
// g<<endl;
//}
//#include<iostream>
//using namespace std;
//int m,i,n,j;
//int main(){
//cin>>n>>m;
//cout<<"{";
//for(i=1;i<=n;i++)
// {
// for(j=1;j<=m;j++)
// if(i==n and j==m)cout<<"("<<i<<","<<j<<")";
// else cout<<"("<<i<<","<<j<<"),";
// }
//cout<<"}";
//return 0;
//}
//#include<iostream>
//using namespace std;
//int k,m,i,n,j,d,x,y,nrd,nrdd;
//int main(){
//cin>>n;
//x=3;
//while(k<n){
// //*verif. x si x+2 prime
// nrd=0;
// for(d=2;d<=x/2;d++)
// if(x%d==0)nrd++;
// y=x+2;
// nrdd=0;
// for(d=2;d<=y/2;d++)
// if(y%d==0)nrdd++;
// if(nrd==0 and nrdd==0){cout<<x<<" "<<x+2<<endl; k++;}
// x+=2;
//}
//return 0;
//}
//#include<fstream>
//#include<cstring>
//using namespace std;
//ifstream f("fis.in");
//ofstream g("fis.out");
//int m,i,n,j;
//char a[10][20];
//int main(){
//f>>n;
//for(i=1;i<=n;i++)
//f>>a[i];
//for(i=n;i>=1;i--)
// {
// m=strlen(a[i]);
// for(j=m-1;j>=0;j--) g<<a[i][j];
// g<<" ";
// }
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("fis.in");
//ofstream g("fis.out");
//struct elev{
// char nume[30],pren[30];
// int n1,n2,n3;
// double med;
//};
//elev e[100];
//int i,n,j;
//double maxi=0;
//int main(){
//f>>n;
//for(i=1;i<=n;i++)
//f>>e[i].nume>>e[i].pren>>e[i].n1>>e[i].n2>>e[i].n3;
//for(i=1;i<=n;i++)
// e[i].med=(double)(e[i].n1+e[i].n2+e[i].n3)/3;
//for(i=1;i<=n;i++)//--afisare-------
//g<<e[i].nume<<" "<<e[i].pren<<" "<< e[i].n1<<" "<<e[i].n2<<" "<<e[i].n3<<" "<<e[i].med<<endl;;
//for(i=1;i<=n;i++)//------maxim---------
// if(e[i].med>maxi ) maxi =e[i].med;
//for(i=1;i<=n;i++)
// if(e[i].med==maxi ) g<<e[i].nume<<" "<<e[i].pren;
//for(i=1;i<=n;i++)//-----ordonare-----
// for(j=i+1;j<=n;j++)
// if(e[i].med>e[j].med)
// swap(e[i],e[j]);
//g<<endl;
//for(i=1;i<=n;i++)
//g<<e[i].nume<<" "<<e[i].pren<<" "<< e[i].n1<<" "<<e[i].n2<<" "<<e[i].n3<<" "<<e[i].med<<endl;;
//
//return 0;
//}
//#include<iostream>//partitii pt. n
//#include<fstream>
//using namespace std;
//ifstream f("pe.in");
//ofstream g("pe.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(int n){
//int j;
//g<<"{";
//for(j=1;j<=n;j++)
// if(a[j]==1)g<<j<<" ";
//g<<"}";
//g<<endl;
//}
//int cont( int k){
//return 1;
//}
//void bt(int k){
// int i;
// if(k==n+1)afiseaza(k-1);
// else
// for(i=0;i<=1;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
//#include<iostream>//partitii pt. n
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(int n){
//int j;
//for(j=1;j<=n;j++)g<<a[j]<<" ";
//g<<endl;
//}
//
//int sol(int k){
//int s=0,i;
//for(i=1;i<=k;i++)s+=a[i];
//if(s==n)return 1;
//else return 0;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(k<=n)return 1;
//else return 0;
//}
//void bt(int k){
// int i;
// if(sol(k-1))afiseaza(k-1);
// else
// for(i=1;i<=n;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
//#include<iostream>//partitii pt. n
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(int n){
//int j;
//for(j=1;j<=n;j++)g<<a[j]<<" ";
//g<<endl;
//}
//
//int suma(int k){
//int s=0,i;
//for(i=1;i<=k;i++)s+=a[i];
//return s;
//}
//int sol(int k){
//if(suma(k)==n)return 1;
//else return 0;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(suma(k)<=n)return 1;
//else return 0;
//}
//void bt(int k){
// int i;
// if(sol(k-1))afiseaza(k-1);
// else
// for(i=1;i<=n;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
//#include<iostream>//permumari
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(){
//int j;
//for(j=1;j<=n;j++)g<<a[j]<<" ";
//g<<endl;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//for(j=1;j<k;j++)
// if (a[j]==a[k]) return 0;
//return 1;
//}
//void bt(int k){
// int i;
// if(k==n+1)afiseaza();
// else
// for(i=1;i<=n;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
//
//#include<iostream>
//using namespace std;
//int a,b;
//int main(){
//cin>>a>>b;
//if(a>b)cout<<"Primul copil este mai mare cu "<<a-b<<" ani";
//if(a<b)cout<<"Al doilea copil este mai mare cu "<<b-a<<" ani";
//if(a==b)cout<<"Copiii au varste egale";
//return 0;
//}
//#include<iostream>//DIVERSE
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,p,i,j,r,m,x,b[100];
//void afiseaza(int k){
//int j;
//for(j=1;j<=k;j++)g<<a[j]<<" ";
//g<<endl;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(a[k]<=a[k-1]) return 0;
//return 1;
//}
//int sol(int k)
//{int kr=0;
// if(k<p) return 0;
// for(int i=1;i<=k;i++)
// if(b[a[i]]==1)kr++;
//
// if(kr<r) return 0;
// return 1;
//}
//void bt(int k){
// int i;
// if(sol(k-1))afiseaza(k-1);
// else
// for(i=1;i<=n;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main()
//{f>>n>>m>>p>>r;
//for(int i=1;i<=m;i++) {f>>x; b[x]=1;}//=1 bila rosie
// bt(1);
//}
//include<iostream>//monede
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],b[100],k,i,j,s;
//void afiseaza(int k){
//int j;
//for(j=1;j<=k-1;j++)
//if(a[j]!=0) g<<b[j]<<" de "<<a[j]<<", ";
//g<<b[j]<<" de "<<a[j]<<"; ";
//g<<endl;
//}
//int sol(int k)
//{int sum=0;
// for(int i=1;i<k;i++)
// sum+=a[i]*b[i];
// if(sum==s)
// return 1;
// else
// return 0;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(k>n) return 0;
//return 1;
//}
//void bt(int k){
// int i;
// if(sol(k))afiseaza(k-1);
// else
// for(i=0;i<=s;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// a[k+1]=0;
// }
//}
//int main(){
// f>>s>>n;
// for(int i=1;i<=n;i++) f>>b[i];
// bt(1);
//}
//#include<iostream>//partitiile unui numar
//#include<fstream>
//using namespace std;
//ifstream f("perm.in");
//ofstream g("perm.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void afiseaza(int k){
//int j;
//for(j=1;j<k;j++)g<<a[j]<<" ";
//g<<endl;
//}
//int sol(int k){
//int j,s=0;
//for(j=1;j<k;j++) s+=a[j];
//if(s==n)return 1;
//else return 0;
//}
//int cont( int k){
//int j; //{verificarea conditiilor de validare}
//if(k>n)return 0;
//return 1;
//}
//void bt(int k){
// int i;
// if(sol(k))afiseaza(k);
// else
// for(i=1;i<=n;i++){
// a[k]=i;
// if(cont(k))bt(k+1);
// }
//}
//int main(){
// f>>n;
// bt(1);
//}
////#include<iostream>//permumari
////#include<fstream>
////using namespace std;
////ifstream f("perm.in");
////ofstream g("perm.out");
////int maxim,n,a[100],k,b[11][11],i,j;
////void afiseaza(){
////int j;
////for(j=1;j<=n;j++)g<<a[j]<<" ";
////g<<endl;
////}
////int cont( int k){
////int j; //{verificarea conditiilor de validare}
////for(j=1;j<k;j++)
//// if (a[j]==a[k]) return 0;
////return 1;
////}
////void bt(int k){
//// int i;
//// if(k==n+1)afiseaza();
//// else
//// for(i=1;i<=n;i++){
//// a[k]=i;
//// if(cont(k))bt(k+1);
//// }
////}
////int main(){
//// f>>n;
//// bt(1);
////}
//#include<iostream>
//#include<cmath>
//using namespace std;
//int i,n,s,x,k,p;
//int main(){
//cin>>p>>n;
//for(i=0;pow(p,i)<=n;i++)
// cout<<pow(p,i)<<" ";
// return 0;
//}
//#include<iostream>
//using namespace std;
//int i,n,s,x,k;
//int main(){
//do{
// cin>>x;//do while
// if(x!=0)
// if(x%2==0)k++;
// }while(x!=0);
// cout<<k;
//
//cin>>x;//while
//while(x!=0){
// if(x%2==0)k++;
// cin>>x;
// }
// if(k>0)cout<<k;
// else cout<<"NU EXISTA";
// return 0;
//}
//#include<iostream>
//using namespace std;
//int i,n,s,x;
//int main(){
//// cin>>n;
//// for(i=1;i<=n;i++)
//// {
//// cin>>x;
//// s+=x;
//// }
//// cout<<s;
////cin>>n;
////i=1;
////while(i<=n){
//// cin>>x;
//// s+=x;
//// i++;
//// }
//// cout<<s;
//cin>>n;
//i=1;
//do{
// cin>>x;
// s+=x;
// i++;
// }while(i<=n);
// cout<<s;
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("roboti1.in");
//ofstream g("roboti1.out");
//struct robot{
// int i,j;
// char d;
// int ok;
//};
//int dir,fr[51][51],a[51][51],p,q,i,n,m,k;
//char b[51][51];
//robot r[100];
//int main(){
// f>>p>>q;
// f>>n;
// for(k=1;k<=n;k++)f>>r[k].i>>r[k].j>>r[k].d;
// f>>m;
// for(k=1;k<=n;k++)f>>b[k];
// for(k=1;k<=n;k++)g<<b[k]<<" ";
// for(k=1;k<=m;k++){
// for(t=1;t<=n;t++)
// {
// comanda=b[k][t];
// if(comanda=='F'){
// if(r[t].d=='N')r[t].i--;
// if(r[t].d=='S')r[t].i++;
// if(r[t].d=='E')r[t].j++;
// if(r[t].d=='V')r[t].j--;
// fr[r[t].i][r[t].j]++;
// a[r[t].i][r[t].j]+=1;
//
// }
// if(comanda=='R'){
// if(r[t].d=='N')r[t].d='E';
// else if(r[t].d=='E')r[t].d='S';
// else if(r[t].d=='S')r[t].d='V';
// else if(r[t].d=='V')r[t].d='N';
// }
// if(comanda=='L'){
// if(r[t].d=='N')r[t].d='V';
// else if(r[t].d=='V')r[t].d='S';
// else if(r[t].d=='S')r[t].d='E';
// else if(r[t].d=='E')r[t].d='N';
// }
//
// }
// return 0;
//}
//#include<iostream>
//#include<fstream>
//using namespace std;
//int maxi,cif,fr[300],i;
//char c;
//int main(){
//c=cin.get();
//while(c!='\n'){
// if(c>='0' and c<='9')fr[(int)c]++;
// c=cin.get();
//}
//for(i=0;i<=127;i++)
// if(fr[i]>maxi){maxi=fr[i];cif=i;}
//if(maxi)cout<<(char)cif;
//else cout<<"NU";
//}
//#include<iostream>//permumari
//#include<fstream>
//using namespace std;
//ifstream f("shuffle.in");
//ofstream g("shuffle.out");
//int sol,n,a[100],k,b[11],i,j;
//void calc_maxim(int k){
//int i,j,m;
//m=k-1;
//for(j=1;j<m;j++) //b[j] b[j+1]
// for(i=1;i<m;i++) //a[i] a[i+1]
// {
// if(b[j]==a[i] and b[j+1]==a[i+1])return;
// if(b[j]==a[i+1] and b[j+1]==a[i])return;
// }
// sol++;
// for(i=1;i<=m;i++)g<<a[i]<<" ";
//g<<endl;
//}
//int cont( int k){
//int ok,j;
//
//ok=1; //{verificarea conditiilor de validare}
//for(j=1;j<k;j++)
// if (a[j]==a[k]) ok=0;
//return ok;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// calc_maxim(k);
// k--; //{revenire}
// }
// else
// if (a[k]<n) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// k=1;cout<<a;
// f>>n;
// for(int i=1;i<=n;i++)f>>b[i];
// backtr();
// if(sol==0)g<<"nu exista";
//}
//#include<iostream>//permumari
//#include<fstream>
//using namespace std;
//ifstream f("summax.in");
//ofstream g("summax.out");
//int maxim,n,a[100],k,b[11][11],i,j,fr[11];
//void calc_maxim(int k){
//int j,s=0;
//for(j=1;j<k;j++)s+=b[j][a[j]];
//if(maxim<s)maxim=s;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// calc_maxim(k);
// k--; //{revenire}
// }
// else
// if (a[k]<n) //exista_suc - ce valori dau lui a[k]????
// {
// fr[a[k]]=0;
// a[k]++;
// if(fr[a[k]]==0) //precizeaza daca sol. partiala este buna
// {fr[a[k]]=1;k++;a[k]=0;}
// }
// else {fr[a[k]]=0; k--;fr[a[k]]=0;}//revenire cand nu exista succesor
//}
//int main(){
// k=1;
// f>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)f>>b[i][j];
//// for(i=1;i<=n;i++)
//// {
//// for(j=1;j<=n;j++)g<<b[i][j]<<" ";
//// g<<'\n'; //g<<endl;
//// }
// backtr();
// g<<maxim;
//}
//#include<iostream>//permumari
//#include<fstream>
//using namespace std;
//ifstream f("summax.in");
//ofstream g("summax.out");
//int maxim,n,a[100],k,b[11][11],i,j;
//void calc_maxim(int k){
//int j,s=0;
//for(j=1;j<k;j++)s+=b[j][a[j]];
//if(maxim<s)maxim=s;
//}
//int cont( int k){
//int ok,j;
//
//ok=1; //{verificarea conditiilor de validare}
//for(j=1;j<k;j++)
// if (a[j]==a[k]) ok=0;
//return ok;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// calc_maxim(k);
// k--; //{revenire}
// }
// else
// if (a[k]<n) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// k=1;
// f>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)f>>b[i][j];
//// for(i=1;i<=n;i++)
//// {
//// for(j=1;j<=n;j++)g<<b[i][j]<<" ";
//// g<<'\n'; //g<<endl;
//// }
// backtr();
// g<<maxim;
//}
//#include<iostream>
//using namespace std;
//int d,x,i,n,k,s;
//int main(){
// cin>>n;
// for(i=2;i<=n;i++)
// {
// x=i;
// k=0;
// for(d=2;d<=x/2;d++)
// if(x%d==0)k++;
// if(k==0)cout<<i<<" ";
// }
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("renju.in");
//ofstream g("renju.out");
//int a[25][25],i,j,n,k,poz,s,el,ok,pi,pj,elsol,ii,jj;
//int main(){
// for(i=1;i<=19;i++)
// for(j=1;j<=19;j++)
// f>>a[i][j];
// for(i=1;i<=19 and ok==0;i++)
// for(j=1;j<=19 and ok==0;j++)
// if(a[i][j]!=0){
// el=a[i][j];
// if(a[i][j-1]!=el){//jj-dreapta
// jj=j;k=0;while(a[i][jj]==el)jj++,k++;
// if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
// }
//
// if(a[i-1][j]!=el){//ii-jos
// ii=i;k=0;while(a[ii][j]==el)ii++,k++;
// if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
// }
// if(a[i-1][j-1]!=el){//diagonala ij ij
// ii=i;jj=j;k=0;while(a[ii][jj]==el)ii++,jj++,k++;
// if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
// }
// if(a[i-1][j+1]!=el){//diagonala dreapta ij ij
// ii=i;jj=j;k=0;while(a[ii][jj]==el)ii++,jj--,k++;
// if(k==5){pi=ii-1; pj=jj+1;elsol=el; ok=1;}
//
// }
// }
// if(elsol!=0) g<<elsol<<'\n'<<pi<<' '<<pj;
//else
//g<<0;
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("marcare.in");
//ofstream fout("marcare.out");
//int a[300],b[300],i,j,n,k,poz,s,nr_el;
//int main(){
//fin>>n>>s>>k;
//for(i=1;i<=n;i++)a[i]=i;
//poz=s;nr_el=1;
//b[poz]=1;fout<<a[poz]<<" ";
//for(i=1;i<=n;i++){
// poz=poz+k;
// if(poz>n)poz=poz-n;
// if(b[poz]==1)break;
// b[poz]=1;
// fout<<a[poz]<<" ";
// nr_el++;
//}
//fout<<endl;
//fout<<n-nr_el;
//return 0;
//}
//
//#include<iostream>//aranjamente
//using namespace std;
//int n,a[100],k,p,b[100][100],m,j;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<b[j][a[j]]<<" ";
//cout<<endl;
//}
//int cont( int k){
//return 1;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<b[k][0]) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cout<<"numar de multimi ";cin>>n;k=1;
// for(int i=1;i<=n;i++){
// cout<<"nr. elemente multime "<<i<<" ";
// cin>>m; b[i][0]=m;
// for(j=1;j<=m;j++) cin>>b[i][j];
// }
// for(int i=1;i<=n;i++){
// for(j=0;j<=b[i][0];j++) cout<<b[i][j]<<" ";
// cout<<endl;
// }
// backtr();
//}
////#include<iostream>//produs cartizian
//using namespace std;
//int n,a[100],k,p,b[100],i;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<a[j]<<" ";
//cout<<endl;
//}
//int cont( int k){
//return 1;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<b[k]) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>n;k=1;
// for(i=1;i<=n;i++)cin>>b[i];
// backtr();
//}
//#include<iostream>//produs cartezian
//using namespace std;
//int n,a[100],k,b[100];
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<a[j]<<" ";
//cout<<endl;
//}
//int cont( int k){
//int ok,j;
//
//return 1; //{verificarea conditiilor de validare}
//
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<b[k]) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>n;k=1;
// for(int i=1;i<=n;i++)
// cin>>b[i];
// backtr();
//}
//
//#include<iostream>//bile
//using namespace std;
//int n,a[100],k,m;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)
// if(a[j]==1)cout<<'r'<<" ";
// else cout<<'v'<<" ";
//cout<<endl;
//}
//int cont( int k){
//int ok,j;
// //{verificarea conditiilor de validare}
//ok=1;
//if (a[k-1]==1 and a[k]==1) ok=0;
//if(k>n+m)return 0;
//return ok;
//}
//int sol(int k){
//
//int i,nr=0,nv=0;
//for(i=1;i<k;i++)
// if(a[i]==1)nr++;
// else nv++;
//if(nr!=m or nv!=n)return 0;
//return 1;
//}
//void backtr(){
// while(k>0)
// if (k==n+m+1 and sol(k)){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<2) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>m>>n;k=1;
// backtr();
//
//}
//
//#include<iostream>//
//using namespace std;
//int n,a[100],k,p,m;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<a[j]<<" ";
//cout<<endl;
//}
//int cont( int k){
//int j,nr1=0,nr2=0;
//if(a[k-1]==2 and a[k]==2)return 0;
//for(j=1;j<=k;j++)
// if(a[j]==1)nr1++;
// else nr2++;
//if(nr1>m or nr2>n)return 0;
//return 1;
//}
//void backtr(){
// while(k>0)
// if (k==p+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<2) //exista_suc
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>n>>m;
// p=n+m;
// k=1;
// backtr();
//}
//#include<iostream>//numerele de n cifre cu cif. in ordine crescatoare
//using namespace std;
//int n,a[100],k;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<a[j]<<" ";
//cout<<endl;
//}
//int cont( int k){
//if(a[k-1]<a[k])return 1;
//else return 0;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<9) //exista_suc
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>n;k=1;
// backtr();
//}
//#include<iostream>//permumari
//using namespace std;
//int n,a[100],k;
//void afisare(int k){
//int j;
//for(j=1;j<k;j++)cout<<a[j]<<" ";
//cout<<endl;
//}
//int cont( int k){
//int ok,j;
//
//ok=1; //{verificarea conditiilor de validare}
//for(j=1;j<k;j++)
// if (a[j]==a[k]) ok=0;
//return ok;
//}
//void backtr(){
// while(k>0)
// if (k==n+1){//sol()
// afisare(k);
// k--; //{revenire}
// }
// else
// if (a[k]<n) //exista_suc - ce valori dau lui a[k]????
// {
// a[k]++;
// if(cont(k)) //precizeaza daca sol. partiala este buna
// {k++;a[k]=0;}
// }
// else k--;//revenire cand nu exista succesor
//}
//int main(){
// cin>>n;k=1;
// backtr();
//
//}
//
//#include <fstream>
//using namespace std;
//ifstream fi("nrlipsa.in");
//ofstream fo("nrlipsa.out");
//int a[1000],i,j,p,q,k,x;
//int main(){
//while(fi>>x)
// if(x>=100 and x<=999)a[x]++;
//k=2;
//for(i=999;i>=100 and k;i--)
// if(a[i]==0){k--;
// if(k==1)p=i;
// else q=i;
// }
//if(k==0)fo<<p<<" "<<q;
//else fo<<"NU";
// return 0;
//}
//
//#include <iostream>
//#include <cmath>
//
//using namespace std;
//
//struct Nod
//{
// int grad;
// float coef;
// Nod* urm;
//};
//
//
//Nod* adauga(Nod *v, float coef, int grad)
//{
// Nod *c=new Nod;
// c->grad=grad;
// c->coef=coef;
// if(v)
// {
// c->urm=v->urm;
// v->urm=c;
// return c;
// }
// else
// {
// c->urm=0;
// return c;
// }
//}
//
//
//Nod* creeaza()
//{
// int n,i; Nod *c=0,*cap=0;
// cout<<"numar termeni:";cin>>n;
// int gr; float coef;
// for(i=1;i<=n;i++)
// {
// cout<<"coeficient:";cin>>coef;
// cout<<"grad:";cin>>gr;
// c=adauga(c,coef,gr);
// if(cap==0) cap=c; //se creaza primul nod
// }
// return cap;
//}
//
//
//void afiseaza(Nod *cap)
//{
// cout<<endl;
// Nod *c=cap;
// if (c==0) cout<<"polinomul e vid";
// int k=0;
// while(c)
// {
// //if(k)
// if (c->coef>0) cout<<"+";
// else cout<<"-";
// cout<<" "<<abs(c->coef)<<"X"<<c->grad<<" " ;
// c=c->urm;
// // k=1;
// }
// cout<<endl;
//}
//
//Nod* Aduna (Nod* p1, Nod *p2)
//{
// Nod *c1=p1,*c2=p2;
// Nod *cap=0,*c=0;
// while(c1!=0 && c2!=0)
// {
// if(c1->grad == c2->grad)
// {
// if(c1->coef + c2->coef)
// c=adauga(c,c1->coef+c2->coef,c1->grad);
// c1=c1->urm; c2=c2->urm;
// }
// else
// if (c1->grad > c2->grad)
// {
// c=adauga(c,c1->coef,c1->grad);
// c1=c1->urm;
// }
// else
// {
// c=adauga(c,c2->coef,c2->grad);
// c2=c2->urm;
// }
// if(cap==0) cap=c; //retinem capul listei
// }
// if(c1)
// while(c1)
// {
// c=adauga(c, c1->coef, c1->grad);
// c1=c1->urm;
// }
// else
// while(c2)
// {
// c=adauga(c, c2->coef, c2->grad);
// c2=c2->urm;
// }
// return cap;
//}
//
//
//Nod* Negativ(Nod *p)
//{
// Nod* c=0,*cap=0;
// while(p)
// {
// c=adauga(c,-(p->coef),p->grad);
// if(cap==0) cap=c;
// p=p->urm;
// }
// return cap;
//}
//
//
//void distruge( Nod* &cap)
//{ Nod* c=cap;
// while(cap)
// {
// cap=cap->urm;
// delete c;
// c=cap;
// }
//}
//int main()
//{
// Nod* p1=creeaza();
//
// Nod* p2=creeaza();
// cout<<endl<<"primul polinom";afiseaza(p1);
// cout<<endl<<"al doilea polinom";afiseaza(p2);
//
//
// Nod* s= Aduna(p1,p2);
// cout<<endl<<"suma polinoamelor";afiseaza(s);
//
// Nod* x= Negativ(p2);
// Nod* d = Aduna(p1,x) ;
// distruge(x);
// cout<<endl<<"diferenta polinoamelor";afiseaza(d);
// return 0;
//}
bodnariuc danut danutbod