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\) là lá bài đầu tiên và \(r\) là lá bài cuối cùng của đoạn (hay nói cách khác, đoạn \((l, r)\) sẽ gồm các lá bài \(a_l, a_{l+1}, \dots, a_r\)). 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ó 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ài nhấ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ữ liệu vào từ tệp văn bản BEAUTY.inp:
  • Dòng đầu tiên gồm ba số nguyên dương \(n, k, \theta\) (\(1 \le n \le 10^6\), \(1 \le k \le 10^{15}\), \(1 \le \theta \le 2\)).
    • Nếu \(\theta = 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 \(\theta = 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_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• Ghi ra tệp văn bản BEAUTY.out:
  • Một dòng duy nhất gồm \(n\) số nguyên không âm:
    • Nếu \(\theta = 1\), số nguyên thứ \(i\) 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 \(\theta = 2\), số nguyên thứ \(i\) 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.

Example

5 20 1
3 5 7 9 20

4 3 3 2 1

5 20 2
3 5 7 9 20

4 2 2 2 0

Scoring

• \(20\%\) số điểm có \(n \le 200\).
• \(20\%\) số điểm khác có \(n \le 5000\) và \(\theta = 1\).
• \(20\%\) số điểm khác có \(n \le 5000\) và \(\theta = 2\).
• \(20\%\) số điểm khác có \(\theta = 1\).
• \(20\%\) số điểm còn lại có \(\theta = 2\).