FFT（Fast Fourier Transformation）是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。是我们在数字信号处理技术中经常会提到的一个概念。在大学的理工科课程中，在完成高等数学的课程后，数字信号处理一般会作为通信电子类专业的专业基础课程进行学习，原因是其中涉及了大量的高等数学的理论推导，同时又是各类应用技术的理论基础。

        傅立叶是一位法国数学家和物理学家的名字，英语原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier对热传递很感兴趣，于1807年在法国科学学会上发表了一篇论文，运用正弦曲线来描述温度分布，论文里有个在当时颇具争议性的命题：任何连续周期信号可以由一组适当的正弦曲线组合而成。当时审查这个论文的人，其中有两位是历史上著名的数学家拉格朗日(Joseph Louis Lagrange, 1736-1813)和拉普拉斯(Pierre Simon deLaplace, 1749-1827)，当拉普拉斯和其他审查者投票通过并要发表这个论文时，拉格朗日坚决反对，在近50年的时间里，拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。法国科学学会屈服于拉格朗日的权威，拒绝了傅立叶的工作，幸运的是，傅立叶还有其它事情可忙，他参加了政治运动，随拿破仑远征埃及，法国大革命后因为怕被推上断头台而一直在逃难。直到拉格朗日死后15年这个论文才被发表出来。

        谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立叶是对的。

        为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替，分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有其他信号所不具备的性质：正弦曲线保真度。一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的，且只有正弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。

        傅立叶变换的物理意义在于，它表明了任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅立叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。当然这是从数学的角度去看傅立叶变换。那么从物理的角度去看待傅立叶变换，它其实是帮助我们改变传统的时间域分析信号的方法转到从频率域分析问题的思维。
        在信息学竞赛中，通常使用它进行计算多项式乘法。现在有两个多项式 f(X)=A₀X⁰+A₁X¹+A₂X²+⋯+A_nXⁿ 和  g(X)=B₀X⁰+B₁X¹+B₂X²+⋯+B_nXⁿ 。 dww学长想知道他们的卷积，但是显然不会给你们出这种题。 

给定一个正整数 n ( 1 <= n <= 100 ) （没有“输入输出1：”这几个字）

输出相应"FFT"图案，具体格式请看样例。