void dft (int nn, int kt, int coile, complex <double> omega)
{
    duzyret[nn].push_back(pus);

    if (nn==1)
    {
        duzyret[nn].back().push_back(duzywek[kt]);
        return;
    }

    dft(nn>>1, kt, coile<<1, omega*omega);
    dft(nn>>1, kt+coile, coile<<1, omega*omega);

    complex <double> jeden (1.0, 0.0);

    for (int i=0; i<nn; i++)
    {
        duzyret[nn].back().push_back(duzyret[nn>>1][0][i%(nn/2)] + jeden*duzyret[nn>>1][1][i%(nn/2)]);
        jeden*=omega;
    }

    duzyret[nn>>1].clear();
}

vector <int> fft(vector <int> jed, vector <int> dwa)
{
    int n1=potenga(jed.size()+dwa.size());
    while(jed.size()<n1)
    {
        jed.push_back(0);
    }
    while(dwa.size()<n1)
    {
        dwa.push_back(0);
    }

    vector < complex <double> > jed1, dwa2, ret;

    for (int i=0; i<n1; i++)
    {
        jed1.push_back(complex <double> ( (double) jed[i] , 0.0 ));
        dwa2.push_back(complex <double> ( (double) dwa[i] , 0.0 ));
    }

    complex <double> omega (cos(2.0*M_PI/n1), sin(2.0*M_PI/n1));

    duzywek=jed1;
    dft(n1, 0, 1, omega);
    jed1=duzyret[n1][0];
    duzyret[n1].clear();

    duzywek=dwa2;
    dft(n1, 0, 1, omega);
    dwa2=duzyret[n1][0];
    duzyret[n1].clear();

    for (int i=0; i<jed1.size(); i++)
    {
        ret.push_back(jed1[i]*dwa2[i]);
    }

    omega=( complex <double> (1.0, 0.0) )/omega;

    duzywek=ret;
    dft(n1, 0, 1, omega);
    ret=duzyret[n1][0];
    duzyret[n1].clear();

    vector <int> retret;
    for (int i=0; i<ret.size(); i++)
    {
        ret[i]/=n1;
        retret.push_back(ret[i].real());
        if (retret.back()+1-ret[i].real()<ret[i].real()-retret.back())
        retret[retret.size()-1]++;
    }
    return retret;
}