--- tags: 卓越盃程式競賽 --- # pD Vile God's Safe ### 題目敘述 卓越大邪神獲得了傅立葉的保險箱，但要解開保險箱需要用到快速傅立葉變換這複雜的手法，為了確保你是否有能力和他一起解開這保險箱，他決定從基本的**多項式函數**開始試煉你，卓越大邪神會給你一個整數n$(1\le n<100000)$接著給你一行含n個整數的數列。 * 定義一個數列$<a_i>^{n-1}_{i=0}(0\le a_i<10^7)$第i項數值代表著的多項式函數$A(x)$第$x^i$項的係數，可被寫作$A(x)=\displaystyle\sum^{n-1}_{i=0}a_ix^i$ 接著卓越大邪神要求你將$A(x)$乘上一多項式函數$B(x)=1+x+x^2+x^3...+x^{n-1}$得到一個新的多項式函數$F(x)=A(x)\times B(x)$，並在桌上擺放**k個保險箱**$(1\le k<10^5)$每個保險箱上都有一數字$q(0\le q<n)$代表著**多項式$F(x)$中的第$x^q$項係數即為此保險箱之密碼**，你能否不辜負卓越大邪神的期望成功在時間內打開所有保險箱呢? ### 輸入說明: - 第一行有兩個整數n$(1\le n<100000)$,k$(1\le k<10^5)$ - 第二行有n個整數，代表一多項式函數項的係數$A(x)=\displaystyle\sum^n_{i=0}a_ix^i(0\le a_i<10^7)$ - 第三行有k個整數$q$ $(0\le q<2n-1)$，代表要查詢$F(x)$的第$x^q$項之係數 ### 輸出說明: - 對於每一筆輸入，請輸出對應的$F(x)$的第$x^q$項之係數 ### Example Input: ``` 3 3 1 2 3 0 2 4 ``` ### Example Output: ``` 1 6 3 ``` ### 配分說明 - $1 \le n \le 1000,1 \le k \le 1000$ 50% - 無限制 50%