Description

We are given a sequence of N positive integers a = [a1, a2, ..., aN] on which we can perform contraction operations.
One contraction operation consists of replacing adjacent elements ai and ai+1 by their difference ai-ai+1. For a sequence of N integers, we can perform exactly N-1 different contraction operations, each of which results in a new (N-1) element sequence.

Precisely, let con(a,i) denote the (N-1) element sequence obtained from [a1, a2, ..., aN] by replacing the elements ai and ai+1 by a single integer ai-ai+1 :

con(a,i) = [a1, ..., ai-1, ai-ai+1, ai+2, ..., aN]
Applying N-1 contractions to any given sequence of N integers obviously yields a single integer.
For example, applying contractions 2, 3, 2 and 1 in that order to the sequence [12,10,4,3,5] yields 4, since : 
con([12,10,4,3,5],2) = [12,6,3,5]

con([12,6,3,5]   ,3) = [12,6,-2]

con([12,6,-2]    ,2) = [12,8]

con([12,8]       ,1) = [4]

Given a sequence a1, a2, ..., aN and a target number T, the problem is to find a sequence of N-1 contractions that applied to the original sequence yields T.

Input

The first line of the input contains two integers separated by blank character : the integer N, 1 <= N <= 100, the number of integers in the original sequence, and the target integer T, -10000 <= T <= 10000.
The following N lines contain the starting sequence : for each i, 1 <= i <= N, the (i+1)st line of the input file contains integer ai, 1 <= ai <= 100.

Output

Output should contain N-1 lines, describing a sequence of contractions that transforms the original sequence into a single element sequence containing only number T. The ith line of the output file should contain a single integer denoting the ith contraction to be applied.
You can assume that at least one such sequence of contractions will exist for a given input.

Sample Input

5 4
12
10
4
3
5

Sample Output

2
3
2
1

 

#include<stdio.h>
#include<string.h>
int dp[103][20004],path[104],a[104];
int main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,-1,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        dp[1][a[1]+10000]=1;
        dp[2][a[1]-a[2]+10000]=0;
        for(i=2;i<n;i++)
            for(j=0;j<=20000;j++)
            {
                if(dp[i][j]>=0)dp[i+1][j+a[i+1]]=1,dp[i+1][j-a[i+1]]=0;
            }
        if(dp[n][m+10000]==1)path[n]=1;
        else path[n]=0;
        int temp=m+10000;
        for(i=n-1;i>=2;i--)
        {
            if(dp[i][temp+a[i+1]]>=0)
            {
                temp=temp+a[i+1];
                path[i+1]=0;
            //    continue;
            }
            else 
            {
                temp=temp-a[i+1];
                path[i+1]=1;
            }
        }
        int k=1;
    //    printf("%d\n",path[2]);
        for(i=3;i<=n;i++)
        {
            if(path[i]==1)
            {
                printf("%d\n",i-k);
                k++;
            }
        }
        for(i=k+1;i<=n;i++)
            printf("1\n");
    }
    return 0;
}