Given a array ~a~ of ~N~ integers and an integer ~M~, find a subsequence of this array such that the alternating sum of this subsequence is maximal, and the absolute difference between any two adjacent elements in the subsequence is at most ~M~.

If there are multiple solutions, print the lexicographically least.

An array ~b~ is a subsequence of ~a~ if ~b~ can be obtained by deleting some of the elements in ~a~. It is not required to delete any elements.

We define the alternating sum of a subsequence as the result of adding each value at an odd index in the sequence (1-indexed), and subtracting each value at an even index in the sequence.

Imagine a sequence ~b~ of length ~L~:

We define the alternating sum of ~b~ as: ~b_1~ ~-~ ~b_2~ ~+~ ~b_3~ ~-~ ~b_4~ ~+~ ~b_5\ldots b_L~

The inequality ~|b_i - b_{i+1}| \leq M~ must hold for ~(1 \leq i < L)~

Input Specification

The first line will contain ~2~ integers, ~N,M~ ~(1\leq N\leq 2\cdot 10^5,0\leq M\leq2\cdot 10^9)~.

The second line will contain ~N~ integers ~a_i~ ~(-10^9\leq a_i\leq10^9)~.

Output Specification

On the first line, output a single integer, the maximum alternating sum you can obtain.

On the second line, output the indices (1-indexed) of the elements contained in the subsequence.

Subtasks

Subtask 1 (5%)

~N \leq 20~

Subtask 2 (25%)

~N \leq 1000~

Subtask 3 (70%)

No further constraints.

Sample Input 1

4 3
-1 2 3 4

Sample Output 1

4
4

Explanation for Sample 1

The maximum alternating sum is simply ~4~, the only element included is at index 4.

Sample Input 2

5 100
3 -4 -2 -9 10

Sample Output 2

24
1 2 3 4 5

Explanation for Sample 2

The maximum alternating sum is ~3 - (\text{-} 4) + (\text{-} 2) - (\text{-} 9) + 10 = 24~, which can be obtained by choosing elements ~1~,~2~,~3~,~4~ and ~5~ in your subsequence.

Sample Input 3

5 7
3 -4 -2 -9 10

Sample Output 3

14
1 2 3 4

Explanation for Sample 3

The maximum alternating sum is ~3 - (\text{-} 4) + (\text{-} 2) - (\text{-} 9) = 14~, which can be obtained by choosing elements ~1~,~2~,~3~ and ~4~ in your subsequence. Note that the result here differs from that of sample output two due to the ~M~ constraint.