---
# System prepended metadata

title: pD Vile God's Safe
tags: [卓越盃程式競賽]

---

---
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% 
