Cho dãy số nguyên F được cho bởi công thức truy hồi sau:

• ~F_1 = a~ và ~F_2 = b~.
• ~\forall t>2: F_t = F_{t-1} + F_{t-2}~.

Dãy số nguyên ~S = S_1, S_2, ..., S_n~

Trong một phép biến đổi, bạn có thể chọn ~\textbf{1}~ phần tử trong dãy ~F~ và tăng hoặc giảm nó ~1~ đơn vị.

Yêu cầu

Với mỗi ~x~ từ ~1~ đến ~k~, nếu được thực hiện chính xác ~x~ phép biến đổi một cách tối ưu, tìm số lần nhiều nhất có thể mà dãy ~S~ xuất hiện như một dãy con liên tiếp của dãy ~F~.

Chú ý rằng những lần xuất hiện của dãy ~S~ trong dãy ~F~ sau biến đổi có thể chồng chéo nhau (tham khảo test ví dụ để rõ hơn).

Dữ liệu

• Dòng đầu chứa hai số nguyên ~a, b \ (|a|, |b| \leq 10^9)~ - hai phần tử đầu tiên của dãy truy hồi ~F~.
• Dòng thứ hai chứa hai số nguyên ~n, k \ (1 \leq n, k \leq 1000)~ - độ dài của dãy ~S~ và số phép biến đổi tối đa.
• Dòng thứ ba chứa ~n~ số nguyên ~S_i \ (|S_i| \leq 10^9)~ - các phần tử của ~S~.

Kết quả

In ra ~1~ dòng duy nhất gồm ~k~ số nguyên, số thứ ~x~ là số lần xuất hiện nhiều nhất có thể của dãy ~S~ trong dãy ~F~ sau chính xác ~x~ phép biến đổi. Nếu số lần xuất hiện có thể nhiều tùy ý thì in ~-1~.

Ví dụ

Sample Input 1

3 -2
3 6
1 -2 1

Sample Output 1

0 1 1 2 2 2

Giải thích

Dãy ~F=\{3,-2,1,-1,0,-1,-1,-2,-3,-5,...\}~.

• Khi ~x~ = ~1~: Không có cách biến đổi nào làm cho dãy ~S~ trở thành dãy con của ~F~.

• Khi ~x~ = ~2~: Biến đổi dãy ~F~ thành ~\{1,-2,1,-1,0,...\}~ (giảm phần tử đầu tiên ~2~ đơn vị). Khi đó, dãy ~S~ chính là dãy con gồm 3 phần tử đầu tiên của ~F~. Chứng minh được không có cách biến đổi nào khiến ~S~ xuất hiện nhiều hơn 1 lần trong ~F~.

• Khi ~x~ = ~5~: Biến đổi dãy ~F~ thành ~\{1,-2,1,-2,1,-1,0,-2,-3,-5,...\}~. Khi đó, ~S~ xuất hiện đúng 2 lần trong ~F~ (dãy con bắt đầu tại vị trí ~1~ và vị trí ~3~). Chứng minh được không có cách biến đổi nào khiến ~S~ xuất hiện nhiều hơn 2 lần trong ~F~.

Sample Input 2

0 0
1 2
0

Sample Output 2

-1 -1

Giải thích

Dãy ~S = \{0\}~. Dãy ~F = \{0, 0, 0, 0,...\}~

Với ~x=1~ và ~x=2~, tồn tại cách biến đổi ~F~ để dãy ~S~ xuất hiện vô số lần trong dãy ~F~.