Longest Interesting Subsegment

We call a contiguous sequence of 2K elements interesting if both the sum of its first K elements and the sum of its last K elements are at most S. Formally, a subsegment A[i], A[i+1], ..., A[i+2K-1] is interesting if

\( \sum_{j=i}^{i+K-1}A[j] \le S \)
and
\( \sum_{j=i+K}^{i+2K-1}A[j] \le S \).

You are given a sequence \(A\) of length \(N\). For each starting position in \(A\), print the interesting subsegment starting from that position which has the maximum length. In other words, for every \(i\) (0-indexed or 1-indexed as in input), find the maximum K (with \(K \ge 1\)) such that the subsegment \(A[i], A[i+1], \ldots, A[i+2K-1]\) is interesting. If no interesting subsegment exists starting at that position (i.e. if \(i+2K-1 \ge N\) for any \(K\ge1\) or the conditions fail), output -1 for that position.

Note: It is assumed that the array elements are non-negative so that the sums are monotonic with respect to \(K\).

inputFormat

The first line contains two integers \(N\) and \(S\) separated by a space.

The second line contains \(N\) non-negative integers \(A[0], A[1], \ldots, A[N-1]\) separated by spaces.

outputFormat

Output \(N\) lines. For the \(i\)-th line (0-indexed), if there is an interesting subsegment starting at \(A[i]\), print the subsegment (i.e. the consecutive elements) separated by a single space. If no interesting subsegment exists, print -1.

sample

5 5
1 2 3 1 1

1 2 3 1
2 3 1 1
3 1
1 1
-1