//  ____                __                         __     _      ___       _     _     
// /\  _`\   __        /\ \                       /\ \  /' \   /'___`\   /' \  /' \    
// \ \ \L\ \/\_\    ___\ \ \___      __     _ __  \_\ \/\_, \ /\_\ /\ \ /\_, \/\_, \   
//  \ \ ,  /\/\ \  /'___\ \  _ `\  /'__`\  /\`'__\/'_` \/_/\ \\/_/// /__\/_/\ \/_/\ \  
//   \ \ \\ \\ \ \/\ \__/\ \ \ \ \/\ \L\.\_\ \ \//\ \L\ \ \ \ \  // /_\ \  \ \ \ \ \ \ 
//    \ \_\ \_\ \_\ \____\\ \_\ \_\ \__/.\_\\ \_\\ \___,_\ \ \_\/\______/   \ \_\ \ \_\
//     \/_/\/ /\/_/\/____/ \/_/\/_/\/__/\/_/ \/_/ \/__,_ /  \/_/\/_____/     \/_/  \/_/

/**************************************************
 * Fast Algorithm Template by Richard1211.
 * Please submit with C++14 or higher version.
 * Blog on Luogu: https://www.luogu.com.cn/blog/522539/
 * Blog on Byethost: http://Richard1211.byethost5.com/
 * Blog on RBTree's: https://Richard1211.rbtr.ee/
***************************************************/
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC target("avx2")
//open Ofast sometimes
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
//#include <bits/extc++.h>
#else
//#include <ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#endif
//#ifdef __linux__
//#include <sys/mman.h>
//#include <sys/types.h>
//#include <fcntl.h>
//#include <unistd.h>
//#else
//#endif
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
#define YES io.writeln("YES")
#define Yes io.writeln("Yes")
#define yes io.writeln("yes")
#define NO io.writeln("NO")
#define No io.writeln("No")
#define no io.writeln("no")
#define Alice io.writeln("Alice")
#define Bob io.writeln("Bob")
#define Taka io.writeln("Takahashi")
#define Aoki io.writeln("Aoki")
#define PFir io.writeln("First")
#define Pfir io.writeln("first")
#define PSec io.writeln("Second")
#define Psec io.writeln("second")
#define RYES return YES,0
#define RYes return Yes,0
#define Ryes return yes,0
#define RNO return NO,0
#define RNo return No,0
#define Rno return no,0
#define RAlice return Alice,0
#define RTaka return Taka,0
#define RAoki return Aoki,0
#define RBob return Bob,0
#define RFir return PFir,0
#define Rfir return Pfir,0
#define RSec return PSec,0
#define Rsec return Psec,0
#define pb emplace_back
#define gp make_pair
#define gt make_tuple
#define sc(x) static_cast<long long>(x)
#define scu(x) static_cast<unsigned>(x)
#define scU(x) static_cast<unsigned long long>(x)
#define scd(x) static_cast<double>(x)
#define scD(x) static_cast<long double>(x)
#define scr(x) static_cast<char>(x)
#define sci(x) static_cast<int>(x)
#define ALL1(G) G.begin(),G.end()
#define ALL2(G,x) G.begin()+x,G.end()
#define ALL3(G,x,y) G.begin()+x,G.begin()+y
#define RALL1(G) G.rbegin(),G.rend()
#define RALL2(G,x) G.rbegin(),G.rend()+x
#define RALL3(G,x,y) G.rbegin()+x,G.rbegin()+y
#define SIZ(G) sc(G.size())
#define SOR(...) sort(ALL(__VA_ARGS__))
#define REV(...) reverse(ALL(__VA_ARGS__))
#define MIN(...) *min_element(ALL(__VA_ARGS__))
#define MAX(...) *max_element(ALL(__VA_ARGS__))
#define SUM(...) accumulate(ALL(__VA_ARGS__),0LL)
#define LB(G,x) distance(G.begin(),lower_bound(ALL(G),x))
#define UB(G,x) distance(G.begin(),upper_bound(ALL(G),x))
#define UNQ(G)                                              \
sort(ALL(G));                                               \
G.erase(unique(ALL(G)),G.end());
#define For1(a) for(register int i=1,i##_r=(a);i<=i##_r;++i)
#define For2(i,a) for(register int i=1,i##_r=(a);i<=i##_r;++i)
#define For3(i,a,b) for(register int i=(a),i##_r=(b);i<=i##_r;++i)
#define For4(i,a,b,c) for(register int i=(a),i##_r=(b);i<=i##_r;i+=(c))
#define For1R(a) for(register int i=(a);i>=1;--i)
#define For2R(i,a) for(register int i=(a);i>=1;--i)
#define For3R(i,a,b) for(register int i=(a),i##_r=(b);i>=i##_r;--i)
#define For4R(i,a,b,c) for(register int i=(a),i##_r=(b);i>=i##_r;i-=(c))
#define For01(a) for(register int i=0,i##_r=(a);i<i##_r;++i)
#define For02(i,a) for(register int i=0,i##_r=(a);i<i##_r;++i)
#define For03(i,a,b) for(register int i=(a),i##_r=(b);i<i##_r;++i)
#define For04(i,a,b,c) for(register int i=(a),i##_r=(b);i<i##_r;i+=(c))
#define For01R(a) for(register int i=(a)-1;i>=0;--i)
#define For02R(i,a) for(register int i=(a)-1;i>=0;--i)
#define For03R(i,a,b) for(register int i=(a)-1,i##_r=(b);i>=i##_r;--i)
#define For04R(i,a,b,c) for(register int i=(a)-1,i##_r=(b);i>=i##_r;i-=(c))
#define ForN1(a) for(register int i=1;i<=(a);++i)
#define ForN2(i,a) for(register int i=1;i<=(a);++i)
#define ForN3(i,a,b) for(register int i=(a);i<=(b);++i)
#define ForN4(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ForN1R(a) for(register int i=(a);i>=1;--i)
#define ForN2R(i,a) for(register int i=(a);i>=1;--i)
#define ForN3R(i,a,b) for(register int i=(a);i>=(b);--i)
#define ForN4R(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define ForN01(a) for(register int i=0;i<(a);++i)
#define ForN02(i,a) for(register int i=0;i<(a);++i)
#define ForN03(i,a,b) for(register int i=(a);i<(b);++i)
#define ForN04(i,a,b,c) for(register int i=(a);i<(b);i+=(c))
#define ForN01R(a) for(register int i=(a)-1;i>=0;--i)
#define ForN02R(i,a) for(register int i=(a)-1;i>=0;--i)
#define ForN03R(i,a,b) for(register int i=(a)-1;i>=(b);--i)
#define ForN04R(i,a,b,c) for(register int i=(a)-1;i>=(b);i-=(c))
#define For1E(i,a) for(auto &i:a)
#define For2E(x,y,a) for(auto &[x,y]:a)
#define For3E(x,y,z,a) for(auto &[x,y,z]:a)
#define For4E(x,y,z,w,a) for(auto &[x,y,z,w]:a)
#define OverLoad(a,b,c,d,e,...) e
#define Overload(a,b,c,d,...) d
#define For(...) OverLoad(__VA_ARGS__,For4,For3,For2,For1)(__VA_ARGS__)
#define ForR(...) OverLoad(__VA_ARGS__,For4R,For3R,For2R,For1R)(__VA_ARGS__)
#define For0(...) OverLoad(__VA_ARGS__,For04,For03,For02,For01)(__VA_ARGS__)
#define For0R(...) OverLoad(__VA_ARGS__,For04R,For03R,For02R,For01R)(__VA_ARGS__)
#define ForN(...) OverLoad(__VA_ARGS__,ForN4,ForN3,ForN2,ForN1)(__VA_ARGS__)
#define ForNR(...) OverLoad(__VA_ARGS__,ForN4R,ForN3R,ForN2R,ForN1R)(__VA_ARGS__)
#define ForN0(...) OverLoad(__VA_ARGS__,ForN04,ForN03,ForN02,ForN01)(__VA_ARGS__)
#define ForN0R(...) OverLoad(__VA_ARGS__,ForN04R,ForN03R,ForN02R,ForN01R)(__VA_ARGS__)
#define ForE(...) OverLoad(__VA_ARGS__,For3E,For2E,For1E)(__VA_ARGS__)
#define ALL(...) Overload(__VA_ARGS__,ALL3,ALL2,ALL1)(__VA_ARGS__)
#define RALL(...) Overload(__VA_ARGS__,RALL3,RALL2,RALL1)(__VA_ARGS__)
#define ForSubset(msk,s)                                    \
for(register int msk=(s);msk;msk&=msk-1)
#define Inline __inline__ __attribute__ ((always_inline))
#define Test()                                              \
register int TestCount=MultiCase?read():1;                  \
for(register int TestCase=1;TestCase<=TestCount;++TestCase)
#define Tesf() for(register int TestCase=1;TestCase<=t;++TestCase)
#define RD(...) register long long __VA_ARGS__;io.read(__VA_ARGS__)
#define RS(...) string __VA_ARGS__;io.read(__VA_ARGS__)
#define RC(...) char __VA_ARGS__;io.read(__VA_ARGS__)
#define RV(G,n)                                             \
vector<long long>G(n+1);                                    \
For(n){                                                     \
	G[i]=read();                                            \
}
#define RVV(G,n,m)                                          \
vector<long long>G(n+1,vector<long long>m+1)                \
For(n){                                                     \
	For(j,m){                                               \
		G[i][j]=read();                                     \
	}                                                       \
}
#ifdef ONLINE_JUDGE
//when on OJ,close the debug version
//hope code with no bugs.
//think twice,code once.
//timer won't print anything
//don't be TLE or MLE,only AC.
#undef Debug
#undef Setmemory
#define Debug(...) 42
#define Setmemory(tmp) 0
#if __cplusplus>201402L
#define register
#else
//becaus of using c++17 and higher version, register are not allowed to use.
#endif
#else
//open debug version.
//hope code with no bugs.
//because of using c++17, we need to undefine register.
//Debug will print out the things we need.
//Setmemory will set the end memory we need.
#define register
#define Debug(...) cerr << "Debug " << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define Setmemory(Tmp) (Timebot::timer.End=&Tmp,0)
template<typename A,typename B>string to_string(pair<A,B>p);
template<typename A,typename B,typename C>string to_string(tuple<A,B,C>p);
template<typename A,typename B,typename C,typename D>string to_string(tuple<A,B,C,D>p);
string to_string(const string&s){return'"'+s+'"';}
string to_string(const char*s){return to_string((string)s);}
string to_string(bool b){return(b?"true":"false");}
string to_string(vector<bool>v){bool first=true;string res="{";for(int i=0;i<static_cast<int>(v.size());i++){if(!first){res+=", ";}first=false;res+=to_string(v[i]);}res+="}";return res;}
template<size_t N>string to_string(bitset<N>v){string res="";for(size_t i=0;i<N;i++){res+=static_cast<char>('0'+v[i]);}return res;}
template<typename A>string to_string(A v){bool first=true;string res="{";for(const auto&x:v){if(!first){res+=", ";}first=false;res+=to_string(x);}res+="}";return res;}
template<typename A,typename B>string to_string(pair<A,B>p){return"("+to_string(p.first)+", "+to_string(p.second)+")";}
template<typename A,typename B,typename C>string to_string(tuple<A,B,C>p){return"("+to_string(get<0>(p))+", "+to_string(get<1>(p))+", "+to_string(get<2>(p))+")";}
template<typename A,typename B,typename C,typename D>string to_string(tuple<A,B,C,D>p){return"("+to_string(get<0>(p))+", "+to_string(get<1>(p))+", "+to_string(get<2>(p))+", "+to_string(get<3>(p))+")";}
inline void debug_out(){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(Head H,Tail...T){cerr<<" "<<to_string(H);debug_out(T...);}
namespace Timebot{
	//timer will print the time and the memory of the code for you.
	//don't be TLE or MLE,only AC.
	struct Timer{
		bool f,*Beg,*End;
	    clock_t Begin;
	     Timer():Begin(clock()),Beg(&f){}
	    ~Timer(){double t=(clock()-Begin)*1000./CLOCKS_PER_SEC;t>=60000?fprintf(stderr,"Time: %.2lf min\n",t/60000.):t>=1000?fprintf(stderr,"Time: %.2lf s\n",t/1000.):fprintf(stderr,"Time: %.0lf ms\n",t);fprintf(stderr,"Memory: %.3lf MB\n",(End-Beg)/1048576.0);}
	}timer;
}
#endif
constexpr double pi=3.1415926535897932384626433832795;
constexpr double ei=2.7182818284590452353602874713527;
constexpr long long ZR=0;
constexpr long long OE=1;
template<class T>constexpr T Infty=0;
template<>constexpr int Infty<int> =1000000000;
template<>constexpr long long Infty<long long> =2000000000000000000;
template<>constexpr unsigned Infty<unsigned> =1000000000;
template<>constexpr unsigned long long Infty<unsigned long long> =2000000000000000000;
template<>constexpr __int128 Infty<__int128> =__int128(Infty<long long>)*Infty<long long>;
template<>constexpr long double Infty<long double> =2e18;
template<>constexpr __float128 Infty<__float128> =2e18;
template<>constexpr double Infty<double> =2e18;
template<class T>Inline T Min(register T a,register T b){return a<b?a:b;}
template<class T>Inline T Max(register T a,register T b){return a>b?a:b;}
template<class T>inline T Min(initializer_list<T>a){register T x=numeric_limits<T>::max();for(auto &it:a){x=Min(x,it);}return x;}
template<class T>inline T Max(initializer_list<T>a){register T x=numeric_limits<T>::min();for(auto &it:a){x=Max(x,it);}return x;}
template<class T>Inline bool Cmin(register T&a,register T b){return a>b?(a=b,true):false;}
template<class T>Inline bool Cmax(register T&a,register T b){return a<b?(a=b,true):false;}
template<class T>inline bool Cmin(register T&a,initializer_list<T>b){register long long x=a;for(auto &it:b){a=Min(a,it);}return x==a?false:true;}
template<class T>inline bool Cmax(register T&a,initializer_list<T>b){register long long x=a;for(auto &it:b){a=Max(a,it);}return x==a?false:true;}
template<class T>Inline T Abs(register T a){return a>0?a:-a;}
template<class T>Inline T Lowbit(register T x){return(x)&(-x);}
template<class T>Inline void Swap(register T&a,register T&b){return a!=b?b^=a^=b^=a,void():void();}
template<class T>inline T Gcd(T a,T b){return b?Gcd(b,a%b):a;}
template<class T>inline T Lcm(T a,T b){return a*b/Gcd(a,b);}
template<class T>inline T Exgcd(T a,T b,T&x,T&y){if(b==0){x=1;y=0;return a;}T d=Exgcd(b,a%b,x,y);T t=x;x=y;y=t-a/b*y;return d;}
template<class T>inline T ExExgcd(T a,T b,T&x,T&y,T c){if(b==0){x=c;y=0;return a;}T d=ExExgcd(b,a%b,x,y,c);T t=x;x=y;y=t-a/b*y;return d;}
template<class T>inline T Ksc(T a,T b){if(a==0||b==0){return 0;}T ans=0;while(b){if(b&1){ans=a+ans;}a=a+a;b>>=1;}return ans;}
template<class T>inline T Ksc(T a,T b,T p){if(a==0||b==0){return 0;}T ans=0;while(b){if(b&1){ans=(a+ans)%p;}a=(a+a)%p;b>>=1;}return ans;}
template<class T>inline T Ksm(T a,T b,bool f=false){if(a==0){return 0;}if(b==0){return 1;}T ans=1;while(b){if(b&1){ans=!f?a*ans:Ksc(a,ans);}a=!f?a*a:Ksc(a,a);b>>=1;}return ans;}
template<class T>inline T Ksm(T a,T b,T p,bool f=false){if(a==0){return 0;}if(b==0){return 1%p;}T ans=1;while(b){if(b&1){ans=!f?a*ans%p:Ksc(a,ans,p);}a=!f?a*a%p:Ksc(a,a,p);b>>=1;}return ans;}
template<class T>inline T Inv(T x,T p){return Ksm(x,p-2,p);}
template<class T>inline T Fac(T n){if(n==0){return 1;}int ans=1;for(register int i=1;i<=n;++i){ans*=i;}return ans;}
template<class T>inline T Fac(T n,T p){if(n==0){return 1;}register long long ans=1;for(register int i=1;i<=n;++i){ans=ans*i%p;}return ans;}
template<class T>Inline int Popcount(T x,bool f=true){return f?__builtin_popcountll(x):__builtin_popcount(x);}
template<class T>Inline int Prebit(T x,bool f=true){return f?__builtin_clzll(x):__builtin_clz(x);}
template<class T>Inline int Sufbit(T x,bool f=true){return f?__builtin_ctzll(x):__builtin_ctz(x);}
template<class T>Inline int Lowone(T x,bool f=true){return f?__builtin_ffsll(x):__builtin_ffs(x);}
template<class T>Inline int Parity(T x,bool f=true){return f?__builtin_parityll(x):__builtin_parity(x);}
template<class T>Inline bool Isdigit(T ch){return ch>='0'&&ch<='9';}
template<class T>Inline bool Isletter(T ch){return ch>='A'&&ch<='Z'||ch>='a'&&ch<='z';}
template<class T>Inline bool Isupper(T ch){return ch>='A'&&ch<='Z';}
template<class T>Inline bool Islower(T ch){return ch>='a'&&ch<='z';}
template<class T>Inline char Tolower(T ch){return ch-'A'+'a';}
template<class T>Inline char Toupper(T ch){return ch-'a'+'A';}
template<class T>inline void Memset(T*d,long long n,long long s){for(register int i=0;i<=s-1;++i){d[i]=n;}}
template<class T>inline void Bug(T x,string name){cerr<<name<<": "<<x<<endl;}
template<class T>inline void Bug(T x){cerr<<x<<endl;}
template<class T>inline T Sin(register T degree){return sinl(degree*(pi/180));}
template<class T>inline T Cos(register T degree){return cosl(degree*(pi/180));}
template<class T>inline T Tan(register T degree){return tanl(degree*(pi/180));}
template<class T>inline T Asin(register T degree){return asinl(degree)*180.0/pi;}
template<class T>inline T Acos(register T degree){return acosl(degree)*180.0/pi;}
template<class T>inline T Atan(register T degree){return atanl(degree)*180.0/pi;}
template<class T>inline long long Rand(T l,T r){static mt19937_64 Rd(chrono::steady_clock::now().time_since_epoch().count());return uniform_int_distribution<long long>(l,r)(Rd);}
template<class T,class F>inline T Binarysearch(T l,T r,T f,const F &check,bool D=true){T mid,ans;for(mid=(l+r)>>1,ans=f;l<=r;mid=(l+r)>>1){check(mid)?ans=mid,(D?r=mid-1:l=mid+1):(D?l=mid+1:r=mid-1);}return ans;}
template<class T,class F>inline T Binarysearch(T l,T r,T f,double eps,const F &check,bool D=true){T mid,ans;for(mid=(l+r)/2;r-l>eps;mid=(l+r)/2){check(mid)?ans=mid,(D?l=mid:r=mid):(D?r=mid:l=mid);}return ans;}
template<class T>inline void Radixsort(register const int n,T*a,T*b){int r1[0x100],r2[0x100],r3[0x100],r4[0x100];memset(r1,0,sizeof(r1));memset(r2,0,sizeof(r2));memset(r3,0,sizeof(r3));memset(r4,0,sizeof(r4));register int i,tmp_int;register T*j,*tar;for(j=a+1,tar=a+n+1;j!=tar;++j){tmp_int=*(int*)j;++r1[tmp_int&0xff];++r2[(tmp_int>>8)&0xff];++r3[(tmp_int>>16)&0xff];++r4[tmp_int>>24];}for(i=1;i<=0xff;++i){r1[i]+=r1[i-1];r2[i]+=r2[i-1];r3[i]+=r3[i-1];r4[i]+=r4[i-1];}for(j=a+n;j!=a;--j){tmp_int=*(int*)j;b[r1[tmp_int&0xff]--]=*j;}for(j=b+n;j!=b;--j){tmp_int=*(int*)j;a[r2[(tmp_int>>8)&0xff]--]=*j;}for(j=a+n;j!=a;--j){tmp_int=*(int*)j;b[r3[(tmp_int>>16)&0xff]--]=*j;}for(j=b+n;j!=b;--j){tmp_int=*(int*)j;a[r4[tmp_int>>24]--]=*j;}}
template<class T>inline void Radixsort(register const int n,T*a,T*b,bool op){size_t size_of_type=sizeof(T);size_t num_of_buc=size_of_type>>1;unsigned**r=new unsigned*[num_of_buc];register int i,k;for(i=0;i<num_of_buc;++i){r[i]=new unsigned[0x10000];memset(r[i],0,0x10000*sizeof(unsigned));}register unsigned short tmp_us;register T*j,*tar;for(k=0;k<num_of_buc;++k){for(j=a+1,tar=a+n+1;j!=tar;++j){tmp_us=*(((unsigned short*)j)+k);++r[k][tmp_us];}}for(k=0;k<num_of_buc;++k){for(i=1;i<=0xffff;++i){r[k][i]+=r[k][i-1];}}for(k=0;k<num_of_buc;k+=0x2){i=k;for(j=a+n;j!=a;--j){tmp_us=*(((unsigned short*)j)+i);b[r[i][tmp_us]--]=*j;}i|=1;if(i==num_of_buc){break;}for(j=b+n;j!=b;--j){tmp_us=*(((unsigned short*)j)+i);a[r[i][tmp_us]--]=*j;}}for(int i=0;i<num_of_buc;i++){delete[]r[i];}delete[]r;}
template<class T>inline void Radixsort(register const int n,T*a,T*b,bool op1,bool op2){Radixsort(n,a,b,true);reverse(a+1,a+n+1);reverse(upper_bound(a+1,a+n+1,(T)(-0.0)),a+n+1);}
template<int R,int L=0,int M=(L+R>>1),class T>Inline void Unroll(int i,T f){R-L==1?f(L+i):(Unroll<M,L>(i,f),Unroll<R,M>(i,f));}
//inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline long long read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline unsigned long long Read(){unsigned long long x=0;long long f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline bool wrt(int x,char ch='\n'){static char buf[64];static int len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
//inline bool write(long long x,char ch='\n'){static char buf[64];static long long len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
//inline bool Write(unsigned long long x,char ch='\n'){static char buf[64];static long long len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
inline void OF(string s){string IN=s+".in";string OUT=s+".out";freopen(IN.c_str(),"r",stdin);freopen(OUT.c_str(),"w",stdout);}
inline void CF(string s){fclose(stdin);fclose(stdout);}
//#define UseBuffer
struct IO{
#ifdef UseBuffer
	//unlockeds somtimes are a little faster than normals
	//#define fread fread_unlocked
	//#define fwrite fwrite_unlocked
    const static int BUFSIZE=1<<20;
	char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;
	inline char getchar(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}
	inline void putchar(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}
	inline IO&flush(){fwrite(obuf,1,pp-obuf,stdout);fflush(stdout);return*this;}
	IO(){p1=buf,p2=buf,pp=obuf;}
	~IO(){flush();}
#else
	//remember to flush in interactive problems
    //int(*getchar)()=&::getchar_unlocked;
	//int(*putchar)(int)=&::putchar_unlocked;
	int(*getchar)()=&::getchar;
	int(*putchar)(int)=&::putchar;
	inline IO&flush(){fflush(stdout);return*this;};
#endif
	int k=2;
    string sep=" ";
	template<typename Tp,typename std::enable_if<std::is_integral<Tp>::value||std::is_same<Tp,__int128_t>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();s*=f;return ch!=EOF;}
	template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF&&ch!='.')f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();if(ch==EOF)return false;if(ch=='.'){Tp eps=0.1;ch=getchar();while(isdigit(ch))s=s+(ch^48)*eps,ch=getchar(),eps/=10;}s*=f;return ch!=EOF;}
	inline int read(char&c){char ch=getchar();c=EOF;while(isspace(ch)&&ch!=EOF)ch=getchar();if(ch!=EOF)c=ch;return c!=EOF;}
	inline int read(char*c){char ch=getchar(),*s=c;while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}
	inline int read(string&s){s.clear();char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}
	inline int getline(char*c,const char&ed='\n'){char ch=getchar(),*s=c;while(ch!=ed&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}
	inline int getline(string&s,const char&ed='\n'){s.clear();char ch=getchar();while(ch!=ed&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}
	template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}
	template<typename Tp,typename...Ts>int read(Tp&x,Ts&...val){return read(x)&&read(val...);}
	template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>IO&write(Tp x){if(x<0)putchar('-'),x=-x;static char sta[114];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)putchar(sta[--top]);return*this;}
	inline IO&write(const string&str){for(char ch:str)putchar(ch);return*this;}
	inline IO&write(const char*str){while(*str!='\0')putchar(*(str++));return*this;}
	inline IO&write(char*str){return write((const char*)str);}
	inline IO&write(const char&ch){return putchar(ch),*this;}
	template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline IO&write(Tp x){if(x>1e18||x<-1e18){write("[Floating point overflow]");throw;}if(x<0)putchar('-'),x=-x;const static long long pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,100000000000000000,100000000000000000};const auto&n=pow10[k];long long whole=(int)x;double tmp=(x-whole)*n;long long frac=tmp;double diff=tmp-frac;if(diff>0.5){++frac;if(frac>=n)frac=0,++whole;}else if(diff==0.5&&((frac==0U)||(frac&1U)))++frac;write(whole);if(k==0U){diff=x-(double)whole;if((!(diff<0.5)||(diff>0.5))&&(whole&1))++whole;}else{putchar('.');static char sta[20];int count=k,top=0;while(frac){sta[top++]=frac%10+'0';frac/=10,count--;}while(count--)putchar('0');while(top)putchar(sta[--top]);}return*this;}
	template<typename Tp,typename...Ts>inline IO&write(Tp x,Ts...val){write(x);write(sep);write(val...);return*this;}
	template<typename...Ts>inline IO&writeln(Ts...val){write(val...);putchar('\n');return*this;}
	inline IO&writeln(void){putchar('\n');return*this;}
	template<typename Tp>inline IO&writeWith(Tp x,const string&s=" "){write(x),write(s);return*this;}
	inline IO&setsep(const string&s){return sep=s,*this;}
	inline IO&setprec(const int&K){return k=K,*this;}
}io;
//namespace mmapreader{
// 	 inline namespace __private__{int len=0,file=-1;char*addr,*nowp,*buff;}
// 	 inline void prepareread(string filename){file=open(filename.c_str(),O_RDONLY);len=(int)lseek(file,0,SEEK_END);addr=(char*)(mmap(0,len,PROT_READ,MAP_PRIVATE,file,0));close(file);buff=(char*)malloc(len*sizeof(char));memcpy(buff,addr,len);munmap(addr,len);nowp=buff;atexit([&buff](){free(buff);});}
// 	 inline void prepareread(FILE* fileptr){file=fileno(fileptr);len=(int)lseek(file,0,SEEK_END);addr=(char*)(mmap(0,len,PROT_READ,MAP_PRIVATE,file,0));buff=(char*)malloc(len*sizeof(char));memcpy(buff,addr,len);munmap(addr,len);nowp=buff;atexit([&buff](){free(buff);});}
// 	 template<typename T>T checked_read(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static T n,s;n=0,s=1;while((*nowp>'9'||*nowp<'0')&&(nowp-buff<len)){if(*nowp=='-')s=-s;nowp++;}if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len)){n=10*n+(*nowp-'0');nowp++;}return n*s;}
// 	 template<typename T>T unchecked_read(){static T n,s;n=0,s=1;while(*nowp>'9'||*nowp<'0'){if(*nowp=='-')s=-s;nowp++;}while(*nowp<='9'&&*nowp>='0'){n=10*n+(*nowp-'0');nowp++;}return n*s;}template<> string checked_read<string>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static string s;s="";while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))nowp++;if(nowp-buff>=len)throw overflow_error("Read out of range!");while(!(*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))s+=*(nowp++);return s;}
// 	 template<> string unchecked_read<string>(){static string s;s="";while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))nowp++;while(!(*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))s+=*(nowp++);return s;}
// 	 template<> char checked_read<char>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))nowp++;if(nowp-buff>=len)throw overflow_error("Read out of range!");return *(nowp++);}
// 	 template<> char unchecked_read<char>(){while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))nowp++;return *(nowp++);}
// 	 template<>long double checked_read<long double>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static long double x,s,n,p;static char*oc;oc=nowp,x=0,s=1,n=0,p=1;while((*nowp>'9'||*nowp<'0')&&(nowp-buff<len)){if(*nowp=='-')s=-s;nowp++;}if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len)){n=10*n+(*nowp-'0');nowp++;}if(nowp-buff>=len||(*nowp!='.'&&*nowp!='e'&&*nowp!='E'))return n*s;if(*nowp=='E'||*nowp=='e'){nowp++;while(*nowp=='-')p=-p,nowp++;if(nowp-buff>=len)return nowp=oc,n*s;while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len))x=10*x+(*nowp-'0'),nowp++;return n*powl(10.0l,x*p);}nowp++;while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len))x=10*x+(*nowp-'0'),nowp++;return n+x/powl(10.0l,floorl(log10l(x)+1));}
// 	 template<>long double unchecked_read<long double>(){static long double x,s,n,p;static char*oc;oc=nowp,x=0,s=1,n=0,p=1;while(*nowp>'9'||*nowp<'0'){if(*nowp=='-')s=-s;nowp++;}while((*nowp<='9'&&*nowp>='0')){n=10*n+(*nowp-'0');nowp++;}if(nowp-buff>=len||(*nowp!='.'&&*nowp!='e'&&*nowp!='E'))return n*s;if(*nowp=='E'||*nowp=='e'){nowp++;while(*nowp=='-')p=-p,nowp++;while(*nowp<='9'&&*nowp>='0')x=10*x+(*nowp-'0'),nowp++;return n*powl(10.0l,x*p);}nowp++;while(*nowp<='9'&&*nowp>='0')x=10*x+(*nowp-'0'),nowp++;return n+x/powl(10.0l,floorl(log10l(x)+1));}
// 	 template<>float checked_read<float>(){return checked_read<long double>();}template<>float unchecked_read<float>(){return unchecked_read<long double>();}
// 	 template<>double checked_read<double>(){return checked_read<long double>();}
// 	 template<>double unchecked_read<double>(){return checked_read<long double>();}
// 	 template<typename T>T checked_read(T& val){return val=checked_read<T>();}
// 	 template<typename T>T unchecked_read(T& val){return val=unchecked_read<T>();}
// 	 template<typename T,typename... args>T checked_read(T& val,args&... ar){return val=checked_read<T>(),checked_read(ar...);}
// 	 template<typename T,typename... args>T unchecked_read(T& val,args&... ar){return val=unchecked_read<T>(),unchecked_read(ar...);}
//}
//namespace mmapwriter{
// 	 int maxsize=5000000,floatpos=11;
// 	 bool truncate=true;
// 	 inline namespace __private__{int len=0,file=-1;char*addr,*nowp,*buff;}
// 	 inline void preparewrite(string filename){buff=(char*)malloc(maxsize*sizeof(char));nowp=buff;file=open(filename.c_str(),O_RDWR|O_CREAT,00777);atexit([&len,&file,&addr,&buff](){/*write(file,buff,len);*/lseek(file,len-1,SEEK_END);write(file,"",1);addr=(char*)mmap(0,len,PROT_READ|PROT_WRITE,MAP_SHARED,file,0);close(file);memcpy(addr,buff,len);munmap(addr,len);});}inline void prepare(FILE* fileptr){buff=(char*)malloc(maxsize*sizeof(char));nowp=buff;file=fileno(fileptr);atexit([&len,&file,&addr,&buff](){write(file,buff,len);});}
// 	 template<typename T>bool write(T val){if(val<0)write('-'),val=-val;if(val>9)write<T>(val/10);*nowp='0'+val%10,nowp++,len++;return true;}
// 	 template<> bool write<char>(char val){*nowp=val,nowp++,len++;return true;}
// 	 template<> bool write<const char*>(const char*val){for(int i=0;i<strlen(val);i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<> bool write<char*>(char*val){for(int i=0;i<strlen(val);i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<> bool write<string>(string val){for(int i=0;i<val.size();i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<>bool write<long double>(long double x){static int k=1;if(k==1)return k=0,write(x/10.0l),*(nowp++)=floorl(fmodl(x,10.0l))+'0',len++,(~floatpos||x-floorl(x)>1e-20l?len++,*(nowp++)='.',k--,write((floorl(x)-x)):1),k=1;if(truncate&&k==-1&&fabs(x)<=1e-20l)return len-=2;if(truncate&&k<1&&fabs(x)<=1e-20l)return len--;if(-k>floatpos)return true;if(fabs(x)<=1e-20l)return*(nowp++)='0';if(x<=-1.0l)return*(nowp++)='-',len++,write(-x);if(x<0.0l)return*(nowp++)=-x*10.0l+'0',len++,k--,write(fmodl(x,0.1l)*10.0l);if(x<10.0l)return*(nowp++)=x+'0',len++;return write(x/10.0l),*(nowp++)=floorl(fmodl(x,10.0l))+'0',len++;}
// 	 template<>bool write<float>(float x){return write<long double>(x);}
// 	 template<>bool write<double>(double x){return write<long double>(x);}
// 	 template<typename T>bool writeln(T val){return write(val),write('\n');}
// 	 template<typename T,typename... args>bool write(T val,args... ar){return write(val),write(' '),write(ar...);}
// 	 template<typename T,typename... args>bool writeln(T val,args... ar){return writeln(val),writeln(ar...);}
//}
//#ifdef __linux__
//#define read unchecked_read
//using namespace mmapreader;
//using namespace mmapwriter;
//inline int rd(){return unchecked_read<int>();}
//inline long long read(){return unchecked_read<long long>();}
//inline unsigned long long Read(){return unchecked_read<unsigned long long>();}
//inline bool wrt(int x,char ch='\n'){return write<int>(x),write<char>(ch),true;}
//inline bool write(long long x,char ch='\n'){return write<long long>(x),write<char>(ch),true;}
//inline bool Write(unsigned long long x,char ch='\n'){return write<unsigned long long>(x),write<char>(ch),true;}
//#else
inline int rd(){return io.read<int>();}
inline long long read(){return io.read<long long>();}
inline unsigned long long Read(){return io.read<unsigned long long>();}
template<class T>inline bool wrt(T x){return io.write(x),true;}
template<class T>inline bool Write(T x,string ch="\n"){return io.writeWith(x,ch),true;}
inline bool WRITE(__int128 x,char ch='\n'){if(x<0)io.putchar('-'),x=-x;static char sta[114];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)io.putchar(sta[--top]);io.putchar(ch);return true;}
#define write(...) io.writeln(__VA_ARGS__)
//#endif
#if __cplusplus>201402L
namespace Montgomery{
#define Modulus_Const
#define Modulus_Prime
//if modulus is const,open Montgomery Fast  Version.
//if modulus is not const,open Dynamic Fast Version,if modulus is not prime,open Dynamic Modulus Version.
#ifdef Modulus_Prime
	bool PR=true;
#else
	bool PR=false;
#endif
	namespace Mont32{
		inline constexpr unsigned getroot1(int MOD){unsigned iv=MOD;for(register unsigned i=0;i!=4;++i){iv*=2U-MOD*iv;}return-iv;}
		template<int MOD>struct Mont{
			private:
				unsigned v;static constexpr unsigned r1=getroot1(MOD),r2=-(unsigned long long)(MOD)%MOD;static_assert((MOD&1)==1);static_assert(-r1*MOD==1);static_assert(MOD<(1<<30));
				inline static constexpr unsigned ksmmod(unsigned x,unsigned long long y){unsigned ans=1;for(;y!=0;y>>=1,x=(unsigned long long)(x)*x%MOD){if(y&1){ans=(unsigned long long)(ans)*x%MOD;}}return ans;}
				inline static constexpr unsigned reduce(unsigned long long x){return x+(unsigned long long)(unsigned(x)*r1)*MOD>>32;}
				inline static constexpr unsigned norm(unsigned x){return x-(MOD&-(x>=MOD));}
			public:
				static constexpr unsigned primitive(){unsigned tmp[32]={},cnt=0;constexpr unsigned long long phi=MOD-1;unsigned long long m=phi;for(register unsigned long long i=2;i*i<=m;++i){if(m%i==0){tmp[cnt++]=i;while(m%i==0){m/=i;}}}if(m!=1){tmp[cnt++]=m;}for(register unsigned long long ans=2;ans!=MOD;++ans){bool flag=true;for(register unsigned i=0;i!=cnt&&flag;++i){flag&=ksmmod(ans,phi/tmp[i])!=1;}if(flag){return ans;}}return 0;}
				 Mont()=default;
				~Mont()=default;
				constexpr Mont(unsigned v):v(reduce((unsigned long long)(v)*r2)){}
				constexpr Mont(const Mont&x):v(x.v){}
				inline int getP()const{return MOD;}
				constexpr unsigned get()const{return norm(reduce(v));}
				explicit constexpr operator unsigned()const{return get();}
				explicit constexpr operator int()const{return(int)(get());}
				Mont operator-()const{Mont ans;return ans.v=(MOD<<1&-(v!=0))-v,ans;}
				Mont Inv()const{int x1=1,x3=0,a=get(),b=MOD;while(b!=0){int q=a/b;tie(x1,x3)=make_tuple(x3,x1-x3*q);tie(a,b)=make_tuple(b,a-b*q);}return Mont(x1+MOD);}
				Mont&operator+=(const Mont&x){return v+=x.v-(MOD<<1),v+=MOD<<1&-(v>>31),*this;}
				Mont&operator-=(const Mont&x){return v-=x.v,v+=MOD<<1&-(v>>31),*this;}
				Mont&operator*=(const Mont&x){return v=reduce((unsigned long long)(v)*x.v),*this;}
				Mont&operator/=(const Mont&x){return this->operator*=(x.Inv());}
				#define stO(op) friend Mont operator op(const Mont&x,const Mont&y){return Mont(x)op##=y;}
				stO(+)stO(-)stO(*)stO(/)
				#undef stO
				#define stO(op) friend bool operator op(const Mont&x,const Mont&y){return norm(x.v)op norm(y.v);}
				stO(==)stO(!=)stO(>)stO(<)stO(>=)stO(<=)
				#undef stO
				Mont&operator++(){*this+=1;return*this;}
				Mont&operator--(){*this-=1;return*this;}
				Mont operator++(int){Mont ans(*this);*this+=1;return ans;}
				Mont operator--(int){Mont ans(*this);*this-=1;return ans;}
				Mont Ksm(long long b){Mont ans=1,a=get();while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
				friend istream&operator>>(istream&is,Mont&x){return is>>x.v,x.v=reduce((unsigned long long)(x.v)*r2),is;}
				friend ostream&operator<<(ostream&os,Mont&x){return os<<x.get();}
		};
	}
	namespace Mont64{
		inline constexpr unsigned long long getroot1(long long MOD){unsigned long long iv=MOD;for(register unsigned i=0;i!=5;++i){iv*=2ULL-MOD*iv;}return iv;}
		inline constexpr unsigned long long getroot2(long long MOD){unsigned long long iv=-(unsigned long long)(MOD)%MOD;for(register unsigned i=0;i!=64;++i){if(MOD<=(iv<<=1)){iv-=MOD;}}return iv;}
		template<long long MOD>struct Mont{
			private:
				unsigned long long v;
				static constexpr unsigned long long r1=getroot1(MOD);static constexpr unsigned long long r2=getroot2(MOD);static_assert((MOD&1)==1);static_assert(r1*MOD==1);static_assert(MOD<(1ULL<<63));
				inline static pair<unsigned long long,unsigned long long>mul(unsigned long long x,unsigned long long y){unsigned long long a=x>>32,b=(unsigned)(x),c=y>>32,d=(unsigned)(y),ac=a*c,bd=b*d,ad=a*d,bc=b*c;return make_pair(ac+(ad>>32)+(bc>>32)+((ad&-1U)+(bc&-1U)+(bd>>32)>>32),bd+(ad+bc<<32));}
				inline static unsigned long long mulhi(unsigned long long x,unsigned long long y){unsigned long long a=x>>32,b=(unsigned)(x),c=y>>32,d=(unsigned)(y),ac=a*c,bd=b*d,ad=a*d,bc=b*c;return ac+(ad>>32)+(bc>>32)+((ad&-1U)+(bc&-1U)+(bd>>32)>>32);}
				inline static unsigned long long reduce(const pair<unsigned long long,unsigned long long>&x){unsigned long long ans=x.first-mulhi(x.second*r1,MOD);return ans+(MOD&-(ans>>63));}
				inline static unsigned long long ksmmod(unsigned long long x,unsigned long long y){unsigned long long ans=reduce(make_pair(0,r2));for(x=reduce(mul(x,r2));y!=0;y>>=1,x=reduce(mul(x,x))){if(y&1){ans=reduce(mul(ans,x));}}return reduce(make_pair(0,ans));}
			public:
				inline static unsigned long long primitive(){unsigned long long tmp[128]={},cnt=0;constexpr unsigned long long phi=MOD-1;unsigned long long m=phi;for(register unsigned long long i=2;i*i<=m;++i){if(m%i==0){tmp[cnt++]=i;while(m%i==0){m/=i;}}}if(m!=1){tmp[cnt++]=m;}for(register unsigned long long ans=2;ans!=MOD;++ans){bool flag=true;for(register unsigned i=0;i!=cnt&&flag;++i){flag&=ksmmod(ans,phi/tmp[i])!=1;}if(flag){return ans;}}return 0;}
				 Mont()=default;
				~Mont()=default;
				Mont(unsigned long long v):v(reduce(mul(v,r2))){}
				Mont(const Mont&x):v(x.v){}
				inline long long getP()const{return MOD;}
				inline unsigned long long get()const{return reduce(make_pair(0,v));}
				explicit operator long long()const{return(long long)(get());}
				explicit operator unsigned long long()const{return get();}
				Mont Inv()const{long long x1=1,x3=0,a=get(),b=MOD;while(b!=0){long long q=a/b;tie(x1,x3)=make_tuple(x3,x1-x3*q);tie(a,b)=make_tuple(b,a-b*q);}return Mont(x1+MOD);}
				Mont operator-()const{Mont ans;return ans.v=(MOD&-(v!=0))-v,ans;}
				Mont&operator*=(const Mont&x){return v=reduce(mul(v,x.v)),*this;}
				Mont&operator+=(const Mont&x){return v+=x.v-MOD,v+=MOD&-(v>>63),*this;}
				Mont&operator-=(const Mont&x){return v-=x.v,v+=MOD&-(v>>63),*this;}
				Mont&operator/=(const Mont&x){return this->operator*=(x.Inv());}
				#define stO(op) friend Mont operator op(const Mont&x,const Mont&y){return Mont(x)op##=y;}
				stO(+)stO(-)stO(*)stO(/)
				#undef stO
				#define stO(op) friend bool operator op(const Mont&x,const Mont&y){return reduce(make_pair(0,x.v))op reduce(make_pair(0,y.v));}
				stO(==)stO(!=)stO(>)stO(<)stO(>=)stO(<=)
				#undef stO
				Mont&operator++(){*this+=1;return*this;}
				Mont&operator--(){*this-=1;return*this;}
				Mont operator++(int){Mont ans(*this);*this+=1;return ans;}
				Mont operator--(int){Mont ans(*this);*this-=1;return ans;}
				friend istream&operator>>(istream&is,Mont&x){return is>>x.v,x.v=reduce(mul(x.v,r2)),is;}
				friend ostream&operator<<(ostream&os,Mont&x){return os<<x.get();}
				Mont Ksm(long long b){Mont ans=1,a=get();while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
		};
	}
	namespace DynamicMont{
		using Tp=long long;
		struct Barrett{
			bool f;long long coef,p;
			inline void Setp(long long P){coef=((__int128)1<<64)/(p=P);}
			long long operator() (const long long &x){return PR?x-(((__int128)x*coef)>>64)*p:(x>=2*p?x%p:x>=p&&x<2*p?x-p:x>=0&&x<p?x:x<0&&x>-p?x+p:x%p+p);}
		}Rec;
		template<int DM>struct Mont{
			static Tp MOD;Tp v;
			 Mont()=default;
			~Mont()=default;
			static void Setp(Tp p){MOD=p;Rec.Setp(MOD);}
			inline Tp getP(){return MOD;}
			inline Tp get(){Mont ans=*this;return ans.v;}
			template<class T>inline Tp reduce(const T &x){Tp ans=Rec(x);return ans<0?ans+MOD:ans;}
			template<class T>Mont(const T&x):v(reduce(x)){}
			Mont operator-()const{return Mont(v?MOD-v:0);}
			Mont&operator+=(const Mont&x){return v=reduce(v+x.v),*this;}
			Mont&operator-=(const Mont&x){return v=reduce(v-x.v),*this;}
			Mont&operator*=(const Mont&x){return v=reduce(v*x.v),*this;}
			Mont&operator/=(const Mont&x){return*this*=x.Inv();}
			#define stO(op) friend Mont operator op(const Mont&x,const Mont&y){return Mont(x)op##=y;}
			stO(+)stO(-)stO(*)stO(/)
			#undef stO
			#define stO(op) friend bool operator op(const Mont&x,const Mont&y){return x.v op y.v;}
			stO(==)stO(!=)stO(>)stO(<)stO(>=)stO(<=)
			#undef stO
			Mont&operator++(){*this+=1;return*this;}
			Mont&operator--(){*this-=1;return*this;}
			Mont operator++(int){Mont ans(*this);*this+=1;return ans;}
			Mont operator--(int){Mont ans(*this);*this-=1;return ans;}
			Mont Ksm(long long b)const{Mont ans=1,a=*this;while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
			Mont Inv()const{return Ksm(MOD-2);}
		};
		template<int DM>Tp Mont<DM>::MOD;
	}
#if (defined Modulus_Const)&&(defined Modulus_Prime)
	using namespace Mont64;
	constexpr long long MOD=998244353;
	using Z=Mont<MOD>;
	inline long long Get(long long x){return x>=0?x:x<-MOD?x%MOD+MOD:x+MOD;}
	//use this often,it's safe.
#else
	using namespace DynamicMont;
	using Z=Mont<-1 >;
#endif
	namespace Mathematics{
		struct Combination{
			int n;long long P;vector<Z>inv,fac,ifac;
			Combination(int lim,long long M):n(lim){P=M;inv=vector<Z>(lim+3);fac=vector<Z>(lim+3);ifac=vector<Z>(lim+3);Init();}
			inline void Init(){fac[0]=ifac[0]=1;inv[1]=fac[1]=ifac[1]=1;for(register int i=2;i<=n;++i){inv[i]=(Z)P-(Z)(P/i)*inv[P%i];fac[i]=fac[i-1]*i;ifac[i]=ifac[i-1]*inv[i];}return void();}
			inline Z Inv(long long x){return inv[x];}
			inline Z Fac(long long x){return fac[x];}
			inline Z Ifac(long long x){return ifac[x];}
			inline Z A(long long x,long long y){return x<y||x<0||y<0?0:fac[x]*ifac[y];}
			inline Z C(long long x,long long y){return x<y||x<0||y<0?0:fac[x]*ifac[y]*ifac[x-y];}
		};
	}
	using namespace Mathematics;
}
#else
namespace Montgomery{
#define Modulus_Const
#define Modulus_Prime
//if modulus is const,open Montgomery Fast  Version.
//if modulus is not const,open Dynamic Fast Version,if modulus is not prime,open Dynamic Modulus Version.
#ifdef Modulus_Prime
	bool PR=true;
#else
	bool PR=false;
#endif
    namespace DynamicMont{
		using Tp=long long;
		struct Barrett{
			bool f;long long coef,p;
			inline void Setp(long long P){coef=((__int128)1<<64)/(p=P);}
			long long operator() (const long long &x){return PR?x-(((__int128)x*coef)>>64)*p:(x>=2*p?x%p:x>=p&&x<2*p?x-p:x>=0&&x<p?x:x<0&&x>-p?x+p:x%p+p);}
		}Rec;
		template<int DM>struct Mont{
			static Tp MOD;Tp v;
			 Mont()=default;
			~Mont()=default;
			static void Setp(Tp p){MOD=p;Rec.Setp(MOD);}
			inline Tp getP(){return MOD;}
			inline Tp get(){Mont ans=*this;return ans.v;}
			template<class T>inline Tp reduce(const T &x){Tp ans=Rec(x);return ans<0?ans+MOD:ans;}
			template<class T>Mont(const T&x):v(reduce(x)){}
			Mont operator-()const{return Mont(v?MOD-v:0);}
			Mont&operator+=(const Mont&x){return v=reduce(v+x.v),*this;}
			Mont&operator-=(const Mont&x){return v=reduce(v-x.v),*this;}
			Mont&operator*=(const Mont&x){return v=reduce(v*x.v),*this;}
			Mont&operator/=(const Mont&x){return*this*=x.Inv();}
			#define stO(op) friend Mont operator op(const Mont&x,const Mont&y){return Mont(x)op##=y;}
			stO(+)stO(-)stO(*)stO(/)
			#undef stO
			#define stO(op) friend bool operator op(const Mont&x,const Mont&y){return x.v op y.v;}
			stO(==)stO(!=)stO(>)stO(<)stO(>=)stO(<=)
			#undef stO
			Mont&operator++(){*this+=1;return*this;}
			Mont&operator--(){*this-=1;return*this;}
			Mont operator++(int){Mont ans(*this);*this+=1;return ans;}
			Mont operator--(int){Mont ans(*this);*this-=1;return ans;}
			Mont Ksm(long long b)const{Mont ans=1,a=*this;while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
			Mont Inv()const{return Ksm(MOD-2);}
		};
		template<int DM>Tp Mont<DM>::MOD;
	}
    using namespace DynamicMont;
#if (defined Modulus_Const)&&(defined Modulus_Prime)
	constexpr long long MOD=998244353;
	using Z=Mont<-1>;
    struct SetMod{SetMod(){Z::Setp(MOD);}}SetMOD;
#else
	using Z=Mont<-1>;
#endif
	namespace Mathematics{
		struct Combination{
			int n;long long P;vector<Z>inv,fac,ifac;
			Combination(int lim,long long M):n(lim){P=M;inv=vector<Z>(lim+3);fac=vector<Z>(lim+3);ifac=vector<Z>(lim+3);Init();}
			inline void Init(){fac[0]=ifac[0]=1;inv[1]=fac[1]=ifac[1]=1;for(register int i=2;i<=n;++i){inv[i]=(Z)P-(Z)(P/i)*inv[P%i];fac[i]=fac[i-1]*i;ifac[i]=ifac[i-1]*inv[i];}return void();}
			inline Z Inv(long long x){return inv[x];}
			inline Z Fac(long long x){return fac[x];}
			inline Z Ifac(long long x){return ifac[x];}
			inline Z A(long long x,long long y){return x<y||x<0||y<0?0:fac[x]*ifac[y];}
			inline Z C(long long x,long long y){return x<y||x<0||y<0?0:fac[x]*ifac[y]*ifac[x-y];}
		};
	}
	using namespace Mathematics;
}
#endif
using namespace Montgomery;
using tp=long long;
using i16=short;
using i64=long long;
using i128=__int128;
using u16=unsigned short;
using u32=unsigned;
using u64=unsigned long long;
using u128=unsigned __int128;
using d32=double;
using d64=long double;
using d128=__float128;
template<class T,class Q>using pr=pair<T,Q>;
template<class T=tp,tp x=3>using ar=array<T,x>;
template<class T=tp>using vc=vector<T>;
template<class T=tp>using vvc=vector<vc<T>>;
template<class T=tp>using vvvc=vector<vvc<T>>;
template<class T=tp>using vvvvc=vector<vvvc<T>>;
template<class T=tp>using vvvvvc=vector<vvvvc<T>>;
template<class T=tp>using pqueue=priority_queue<T>;
template<class T=tp>using bqueue=priority_queue<T,vector<T>,greater<T>>;
template<class T=tp,class Q=tp,class R=tp>using tup=tuple<T,Q,R>;
template<class T=tp,class Q=tp,class R=tp,class S=tp>using ttup=tuple<T,Q,R,S>;
template<class T=tp,class Q=tp,class R=tp,class S=tp,class U=tp>using tttup=tuple<T,Q,R,S,U>;
#define vv(T,G,a,...) vvc<T>G(a,vc<T>(__VA_ARGS__))
#define vvv(T,G,a,b,...) vvvc<T>G(a,vvc<T>(b,vc<T>(__VA_ARGS__)))
#define vvvv(T,G,a,b,c,...) vvvvc<T>G(a,vvvc<T>(b,vvc<T>(c,vc<T>(__VA_ARGS__))))
#define vvvvv(T,G,a,b,c,d,...) vvvvvc<T>G(a,vvvvc<T>(b,vvvc<T>(c,vvc<T>(d,vc<T>(__VA_ARGS__)))))
using pt=pr<tp,tp>;
using ar3=ar<tp,3>;
using ar4=ar<tp,4>;
[[maybe_unused]]constexpr long long N=1000100;
constexpr bool MultiCase=false;

bool test_students(vc<bool>mask){
    string mask_str(SIZ(mask),'0');
    For0(SIZ(mask))mask_str[i]=mask[i]?'1':'0';
    cout << "Q "+mask_str << endl;
    char answer;
    cin >> answer;
    return answer=='P';
}
vc<bool>find_positive(tp n,d32 p){
    vc<bool>answer(n);
    auto Query=[&](tp l,tp r){
		vc<bool>G(n);
		fill(ALL(G,l,r),true);
		return test_students(G);
	};
	for(register tp l=0;l<=n-1;114514){
		register tp r=min<tp>(n,l+1/p);
		if(!Query(l,r)){l=r;continue;};
		register tp L=l,R=r,mid;
		while(R-L>1)mid=(l+r)>>1,!Query(l,mid)?L=mid:R=mid;
		answer[L]=true;
		l=L+1;
	}
    return answer;
}
int main(){
	register tp n,t;
	register d32 p;
	cin >> n >> p >> t;
	For($,t){
	    vc<bool>ans=find_positive(n,p);
	    std::string ans_str(SIZ(ans),'0');
	    For0(SIZ(ans))ans_str[i]=ans[i]?'1':'0';
	    cout << "A "+ans_str << endl;
		char verdict;
		cin >> verdict;
        verdict=='W'?exit(0):void();
	}
	return 0;
}