int bitRev(int n, int len) {
	int ans = 0;
	for(int i = 0; i < len; i++) {
		if((n >> i) & 1) {
			ans |= (1 << (len - i - 1));
		}
	}
	return ans;
}

void vSort(vcd &a) {
	int d, n = a.sz, len = log(n + .0) / log(2.0);
	for(int i = 0; i < n; i++) {
		d = bitRev(i, len);
		if(d < i) {
			swap(a[d], a[i]);
		}
	}
}

void fft(vcd &a, bool inv) {
	int n = a.sz;
	vSort(a);

	for(int len = 1; len <= n; len <<= 1) {
		double angle = 2 * PI / len * ((inv) ? -1 : 1);
		vcd precalc(len);
		cd w(1), tmp(cos(angle), sin(angle));

		for(int i = 0; i < len; i++) {
			precalc[i] = w;
			w *= tmp;
		}

		for(int i = 0; i< n; i += len) {
			for(int j = 0; j < len/2; j++) {
				cd u = a[i + j], v = a[i + j +len / 2] * precalc[i + j + len/2];
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
			}
		}
	}

	if(inv) {
		for(int i = 0; i < n; i++) {
			a[i] /= n;
		}
	}
}