Description

There is a deck with a total of $n$ cards. The $i$-th card has a number $a_i$ written on it, where the first card is the top of the deck.

Player Z draws first. He may draw a consecutive number of cards starting from the top of the deck (he may draw $0$ cards). The drawn cards are held in his hand, meaning they are removed from the deck.

Then Player Y draws. Similarly, she may draw a consecutive number of cards starting from the top of the deck (she may draw $0$ cards).

If the sum of the numbers on a player's hand is greater than $X$, then their score is $0$; otherwise, their score equals the sum.

The player with the higher score wins; if the scores are equal, then nobody wins.

In order to win, Player Z uses a cheating tool (x-ray vision), meaning he knows the number written on every card in the deck.

Now, for all integers $X$ satisfying $1 \leq X \leq K$, determine which values of $X$ allow Player Z to have a winning strategy, i.e., after Player Z finishes drawing, no matter how Player Y draws, Player Y will definitely lose.

Input Format

The first line contains an integer $n$, representing the number of cards in the deck.

The second line contains $n$ integers $a_{1\dots n}$, representing the number written on each card.

The third line contains a positive integer $K$, as described in the statement.

Output Format

The first line contains an integer, representing the number of values $X$ that satisfy the requirement.

The second line outputs the values of $X$ that satisfy the requirement in increasing order, separated by spaces.

5
1 4 3 2 2
5

3
1 2 3

Hint

[Sample Explanation]

When $X=1,2,3$, Player Z draws one card, and no matter how Player Y draws, Player Y will get a score of $0$.

When $X=4$, if Player Z draws $1$ card, then if Player Y draws $1$ card, Player Y will win; otherwise, Player Z can only get a score of $0$.

When $X=5$, if Player Z draws $1$ card, then if Player Y draws $1$ card, Player Y will win. If Player Z draws $2$ cards, then Player Y also draws $2$ cards, resulting in a tie. Otherwise, Player Z can only get a score of $0$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (3 points): $n = 1$.
• Subtask 2 (14 points): $K = 1$.
• Subtask 3 (20 points): $n, K \le 100$.
• Subtask 4 (33 points): $n, K \le 3333$.
• Subtask 5 (30 points): no special restrictions.

For $100\%$ of the testdata, $1 \leq n, K \leq 10^6$, $1 \leq a_i \leq K$.

Translated by ChatGPT 5