Code: 

#include
     
      #define ll long long#define maxn 500000 #define setIO(s) freopen(s".in","r",stdin) using namespace std;const double pi=acos(-1.0);struct cpx{    double x,y;    cpx(double a=0,double b=0) {x=a,y=b; }    cpx operator+(const cpx b) { return cpx(x+b.x,y+b.y); }    cpx operator-(const cpx b) { return cpx(x-b.x,y-b.y); }    cpx operator*(const cpx b) { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }A[maxn],B[maxn];                   void FFT(cpx *a,int n,int flag){    for(int i=0,k=0;i
      
       k) swap(a[i],a[k]);        for(int j=n>>1;(k^=j)
       
        >=1);    }    for(int mid=1;mid
        
         <<=1)    {        cpx wn(cos(pi/mid), flag*sin(pi/mid)),x,y;        for(int i=0;i
         
          <<1))                             {            cpx w(1,0);            for(int j=0;j
          
           >1,len,a=0,b=0; for(len=1;len<=(r-l+1);len<<=1); for(int i=0;i<=len;++i) A[i].x=B[i].x=A[i].y=B[i].y=0; for(int i=l;i<=mid;++i) A[a++].x=bucka[i]; for(int i=mid+1;i<=r;++i) B[b++].x=buckb[i]; FFT(A,len,1),FFT(B,len,1); for(int i=0;i