Nhật có ~n~ lá bài, lá bài thứ ~i~ ghi một số nguyên dương ~A_i~. Anh trải các lá bài này thành một hàng ngang (lá bài thứ ~i~ nằm ở vị trí thứ ~i~ từ trái sang) và bắt đầu một thử thách nhỏ với chúng.

Nhật định nghĩa một đoạn các là bài là một tập hợp các lá bài ở các vị trí liên tiếp nhau, có thể được mô tả bằng một cặp số ~(l,r)~, với ~1 \le l \le r \le n~, với ~l, r~ là lá bài đầu tiên và là lá bài cuối cùng của đoạn. Nhật còn định nghĩa hai khái niệm liên quan đến đoạn các lá bài sau:

— Một đoạn được gọi là đẹp nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá ~k~ (nếu một phần không có lá bài nào thì tổng các số của phần đó là 0).

— Một đoạn được gọi là hoàn hảo nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) có số lá bài bằng nhau sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá ~k~ (nếu một phần không có lá bài nào thì tổng các số của phần đó là 0).

Ví dụ, trong dãy các lá bài ~A~ = 1,2,3,3,2,1 và ~k~ = 5 ta có thể các trường hợp ví dụ sau:

— 1,2,2,1 không phải là một đoạn của dãy (vì đây không phải là đoạn gồm các lá bài liên tiếp).

— 1,2,3 là một đoạn đẹp vì có thể chia đoạn này thành hai phần 1,2 và 3 cùng có tổng các số bằng 3. Đây không phải là một đoạn hoàn hảo vì không thể được chia thành hai phần có số lá bài bằng nhau.

— 2,3,3,2 là một đoạn hoàn hảo vì có thể chia đoạn này thành hai phần 2,3 và 3,2 cùng có hai lá bài và có tổng các số ghi trên các lá bài bằng 5.

— Tương tự, 3,3 cũng là một đoạn hoàn hảo. Các đoạn 2,3,3,2 và 3,3 đồng thời cũng là các đoạn đẹp.

— 1,2,3,3,2,1 không phải là một đoạn đẹp vì không tồn tại cách chia nào thỏa mãn.

Thử thách mà Nhật đặt ra cho chính mình như sau: Với mỗi vị trí ~i~ mà ~1 \le i \le n~ , anh phải tìm ra đoạn đẹp dài nhất và đoạn hoàn hảo dàinhất bắt đầu từ vị trí này. Độ dài của một đoạn là số lá bài nằm trong đoạn đó. Nhật đã hoàn thành thử thách nhưng cần phải kiểm tra xem đáp án của mình có đúng hay không. Các bạn hãy viết một chương trình để giúp Nhật kiểm tra kết quả của mình nhé.

Input

— Dòng đầu tiên gồm ba số nguyên dương ~n, k, t~ (~1 \le n \le 10^6, 1 \le k \le 10^{15} , 1 \le t \le 2~)

— Nếu ~t = 1~, bạn cần phải xác định đoạn đẹp dài nhất bắt đầu từ mỗi vị trí i với ~1 \le i \le n~.

— Nếu ~t = 2~, bạn cần phải xác định đoạn hoàn hảo dài nhất bắt đầu từ mỗi vị trí i với ~1 \le i \le n~

— Dòng tiếp theo gồm ~n~ số nguyên dương ~A_i~ (~A_i \le 10^9~)

Output

— Một dòng duy nhất gồm ~n~ số nguyên không âm:

— Nếu ~t = 1~, số nguyên thứ là độ dài đoạn đẹp dài nhất bắt đầu từ vị trí thứ ~i~, hoặc bằng 0 nếu không thể tìm được đoạn đẹp nào.

— Nếu ~t = 2~, số nguyên thứ là độ dài đoạn hoàn hảo dài nhất bắt đầu từ vị trí thứ ~i~, hoặc bằng 0 nếu không thể tìm được đoạn hoàn hảo nào.

Sample Input 1

5 20 1
3 5 7 9 20

Sample Output 1

4 3 3 2 1

Sample Input 2

5 20 2
3 5 7 9 20

Sample Output 2

4 2 2 2 0

Notes

— Subtask 1: 20đ có ~n \le 200~.

— Subtask 2: 20đ khác có ~n \le 5000~ và ~t = 1~.

— Subtask 3: 20đ khác có ~n \le 5000~ và ~t = 2~.

— Subtask 4: 20đ khác có ~t = 1~.

— Subtask 5: 20đ còn lại có ~t = 2~.