
#include "ilist.h"

#include "lagrange.h"


LagrangeSolver* lagrangesolver_new(SCPView* pv,HeuristicType type) {

    LagrangeSolver* ls=NULL;

    /*Check parameters and conditions*/
    assert (pv!=NULL);
    
    /*Create new LagrangeSolver*/
    ls = (LagrangeSolver*)malloc(sizeof(LagrangeSolver));
    assert(ls!=NULL);
    
    /*Allocate space for multipliers*/
    ls->t=(float*)malloc(pv->rows*sizeof(float));
    assert(ls->t!=NULL);
    
    /*Allocate space for p vector*/
    ls->p=(float*)malloc(pv->columns*sizeof(float));
    assert(ls->p!=NULL);
    
    /*Allocate space for x vector*/
    ls->x=(unsigned char*)malloc(pv->columns*sizeof(unsigned char));
    assert(ls->x!=NULL);
    
    /*Allocate space for G vector*/
    ls->G=(int*)malloc(pv->rows*sizeof(int));
    assert(ls->G!=NULL);

    /*List of available columns*/
    ls->availCols=ilist_new_sequence(pv->columns);

    /*Allocate space for best current feasible solution*/
    ls->xf=(unsigned char*)malloc(pv->columns);
    assert(ls->xf!=NULL);

    /*Allocate space for best ever feasible solution*/
    ls->xbest=(unsigned char*)malloc(pv->columns);
    assert(ls->xbest!=NULL);


    /*Allocate space for reduced cost vector*/
    ls->reducedCosts=(float*)malloc(pv->columns*sizeof(float));
    assert(ls->reducedCosts!=NULL);

    ls->modifiedReducedCosts=(float*)malloc(pv->columns*sizeof(float));
    assert(ls->modifiedReducedCosts!=NULL);

    /*Statistics*/
    ls->stIterationCount=0;

    /*Assign problem*/
    ls->problemView=pv;
    
    /*Iteration counters*/
    ls->iterations=0;
    ls->sup_iterations=0;

    /*Heuristic type*/
    ls->heuristicType=type;

    return ls;
}

int lagrangesolver_solve(LagrangeSolver* s,int maxLowerBound,unsigned char fastCancel) {

    int gqsum=0;
    
    /*Check parameters and conditions*/
    assert (s!=NULL);

    s->fastCancel=fastCancel;

    /* --- STEP 1 Initialize ---*/
    lagrangesolver_initialize(s);

    
    
    while(1) {

        

        /*--- STEP 2 Solve LRP with current set of multipliers, update ZLB,ZMAX and x ---*/
        lagrangesolver_solve_lrp(s);

        /*---STEP 3 Solve original SCP with some heuristic, update ZUB ---*/

        if ((s->iterations % 10)==0) {
            lagrangesolver_solve_original(s);
        }

        /*Check ZMAX for maximum lower bound*/
        if (maxLowerBound>0 && s->ZMAX>maxLowerBound) return 0;

        /*--- STEP 4 if ceil(ZMAX) = ZUB then stop ---*/
        if (ceil(s->ZMAX)==s->ZUB) break;
        
        /*--- STEP 5 Removing columns ---*/
        lagrangesolver_removecolumns(s);

        /*No columns available => end*/
        if (s->availCols->length<1) break;
        
        /*--- STEP 6 Calculate subgradient ---*/
        gqsum=lagrangesolver_subgradient(s);
        if (gqsum==0) break;
        
        /*--- STEP 7 Iteration ---*/
        if (lagrangesolver_iteration(s,gqsum)==0) break;
        
    }
    
    return 0;
}

void lagrangesolver_initialize(LagrangeSolver* s) {
    
    int j=0;
    int i=0;
    int cols=0;
    int rows=0;
    
    /*Iteration counters*/
    s->iterations=0;
    s->sup_iterations=0;
    s->iteration_multiplier=2.0f;
    
    /*ZMAX and ZUB negative infinity*/
    s->ZMAX=NEG_INFINITY;
    s->ZUB=POS_INFINITY;
    s->ZLB=0.0f;
    s->sup_ZMAX=NEG_INFINITY;

    cols=s->problemView->columns;
    rows=s->problemView->rows;


    /*x and xf and xbest[0..cols]=0*/
    memset(s->x,0,cols);
    memset(s->xf,0,cols);
    memset(s->xbest,0,cols);
    
    /*Reduced costs 0*/
    memset(s->reducedCosts,0,cols*sizeof(float));
    
    /*Sort rows and columns*/
    lagrangesolver_sort(s);

    /*p[j]=c[j]*/
    for(j=0;j<cols;j++) {
        s->p[j]=scp_view_get_cost(s->problemView,j);
    }
    
    /*t[i]=min (c[j] | data[i][j]=1)
     *That means t[i] is equal to the cost of cheapest column, that covers the
     *row i*/
    
    for(i=0;i<rows;i++) {
        for(j=0;j<cols;j++) {
            if (scp_view_get(s->problemView,i,j)==1) {
                s->t[i]=(float)scp_view_get_cost(s->problemView,j);
                break;
            }
        }
    }

    /*Algorithm is now initialized*/
    
}

void lagrangesolver_solve_lrp(LagrangeSolver* s) {
    
    
    /*Calculate reduced costs of columns and add
     *columns that have these costs negative*/
    int rows = s->problemView->rows;
  
    int columnIndex=0;
    
    
    int i=0;
    float totalcost=0.0f;
    float cred=0.0f;

    ilist_start_iteration(s->availCols);
    while(ilist_iterate(s->availCols,&columnIndex)) {

        

        cred=lagrangesolver_get_reduced_cost(s,columnIndex);
        s->reducedCosts[columnIndex]=cred;
        
        /*If reduced cost is negative, the column is added
         *to the solution
         */
        if (cred<0.0f) {
            s->x[columnIndex]=1;
            totalcost+=cred;
        }
        else {
            s->x[columnIndex]=0;
        }
    }

    for(i=0;i<rows;i++) totalcost+=s->t[i];
    
    /*Update ZMAX*/
    if (totalcost > s->ZMAX) s->ZMAX=totalcost;
    s->ZLB=totalcost;

    
    
}

void lagrangesolver_solve_original(LagrangeSolver* s) {

    switch(s->heuristicType) {
        case LAGRANGE_HEURISTIC_1: {lagrangesolver_ha_beasley(s);break;}
        case LAGRANGE_HEURISTIC_2: {lagrangesolver_ha_reduced_costs_a(s,s->problemView->columns,0);break;}
        case LAGRANGE_HEURISTIC_3: {lagrangesolver_ha_reduced_costs_a(s,s->problemView->columns,1);break;}
        case LAGRANGE_HEURISTIC_4: {lagrangesolver_ha_reduced_costs_b(s,s->problemView->columns,0);break;}
        case LAGRANGE_HEURISTIC_5: {lagrangesolver_ha_reduced_costs_b(s,s->problemView->columns,1);break;}
        default: {assert(0);break;}
    }

}


void lagrangesolver_ha_beasley(LagrangeSolver* s) {

    /*NOTE: Heuristic #1 Plain Beasley heuristic*/

    int cols = s->problemView->columns;
    int rows = s->problemView->rows;

    int columnIndex=0;

    int i=0;
    int uri=-1;  /*Index of found uncovered row*/
    int last=-1;
    int tmp=0;


    float costs;

    /*Copy the x vector*/
    memcpy(s->xf,s->x,cols);

    while(1) {

        /*Select a row which is uncovered*/
        uri=-1;
        for(i=last+1;i<rows;i++) {
            /*Examine whether row is covered by some column from x*/
            tmp=0;
            ilist_start_iteration(s->availCols);
            while(ilist_iterate(s->availCols,&columnIndex)) {
                if (s->xf[columnIndex]==1 && scp_view_get(s->problemView,i,columnIndex)) {
                    tmp=1;
                    break;
                }
                
            }
            /*If not, set the index*/
            if (tmp==0) {
                uri=i;
                last=i;
                break;
            }
        }

        

        if (uri!=-1) {
            /*Row is uncovered. We select the first column that covers
             *our row*/
            
            ilist_start_iteration(s->availCols);
            while(ilist_iterate(s->availCols,&columnIndex)) {
                if (scp_view_get(s->problemView,uri,columnIndex)==1) {
                    s->xf[columnIndex]=1;
                    break;
                }
            }
        }

        else {
            break;  /*All rows are covered now*/
        }

    }

    /*Now we will consider all columns in the xf. We will try to
     *remove them and test whether the solution is valid after column
     *removal*/
    ilist_start_deteration(s->availCols);
    while(ilist_deterate(s->availCols,&columnIndex)) {
        if (s->xf[columnIndex]==0) continue;
        s->xf[columnIndex]=0;
        if (scp_view_is_solution(s->problemView,s->xf)==0) s->xf[columnIndex]=1;
    }

    /*Update ZUB*/
    costs=0.0f;
    ilist_start_iteration(s->availCols);
    while(ilist_iterate(s->availCols,&columnIndex)) {
        if (s->xf[columnIndex]==1) costs+=scp_view_get_cost(s->problemView,columnIndex);
    }

    lagrangesolver_update_zub(s,costs);
    /*Done*/
}

void lagrangesolver_ha_reduced_costs_a(LagrangeSolver* s,int maxCandidates,unsigned char modifiedCost) {

    /*NOTE: Heuristics #2,#3
     *To complete primal (and possibly non-feasible solution),
     *maxCandidates columns are considered. The candidate
     *with lowest reduced cost (heuristic #2) or with lowest modified reduced
     *cost (heuristic #3) is selected
     *
     *Superfluous columns are removed according to their decreasing cost. Columns
     *are already sorted according to their cost
     *
     */
    int cols = s->problemView->columns;
    int rows = s->problemView->rows;

    int i=0;
    int uri=-1;  /*Index of found uncovered row*/
    int last=-1;
    int tmp=0;
    float min;
    float tmp2;
    int minIndex;
    float costs;
    int candidateCounter;

    int columnIndex=0;


    assert(maxCandidates>0 && maxCandidates<=cols);

   

   /*Copy the x vector*/
   memcpy(s->xf,s->x,cols);
   memcpy(s->modifiedReducedCosts,s->reducedCosts,cols*sizeof(float));

   while(1) {

        /*Select a row which is uncovered*/
        uri=-1;
        for(i=last+1;i<rows;i++) {
            /*Examine whether row is covered by some column*/
            tmp=0;
            ilist_start_iteration(s->availCols);
            while(ilist_iterate(s->availCols,&columnIndex)) {
                
                if (s->xf[columnIndex]==1 && scp_view_get(s->problemView,i,columnIndex)) {
                    tmp=1;
                    break;
                }

            }
            /*If not, set the index*/
            if (tmp==0) {
                uri=i;
                last=i;
                break;
            }
        }

        if (uri!=-1) {
            /*Row is uncovered. We select column that hase
             *lowest reduced cost
             */
            min=POS_INFINITY;
            minIndex=-1;
            candidateCounter=0;

            ilist_start_iteration(s->availCols);
            while(ilist_iterate(s->availCols,&columnIndex) && candidateCounter<maxCandidates) {
            
                if (scp_view_get(s->problemView,uri,columnIndex)==1) {
                    /*Candidate found. We calculate reduced cost and check
                     *whether such cost is lowest*/
                    tmp2=s->modifiedReducedCosts[columnIndex];
                    if (tmp2<min) {
                        min=tmp2;
                        minIndex=columnIndex;
                    }
                    candidateCounter++;
                }
            }
            /*What should never happen*/
            assert(minIndex!=-1);
            
            /*Adding selected column to the solution*/
            s->xf[minIndex]=1;

            /*If modified cost heuristic is selected, we change current reduced cost of
             *columns that cover the recently covered row*/
            if (modifiedCost==1) {
                ilist_start_iteration(s->availCols);
                while(ilist_iterate(s->availCols,&columnIndex)) {
                    if (scp_view_get(s->problemView,uri,columnIndex)==1) {
                        s->modifiedReducedCosts[columnIndex]+=s->t[uri];
                    }
                }
            }

        }
        
        else {
            break;  /*All rows are covered now*/
        }

    }

    /*Now we will consider all columns int the xf. We will try to
     *remove them and test whether the solution is valid after column
     *removal*/
   ilist_start_deteration(s->availCols);

    while(ilist_deterate(s->availCols,&columnIndex)) {
        if (s->xf[columnIndex]==0) continue;
        s->xf[columnIndex]=0;
        if (scp_view_is_solution(s->problemView,s->xf)==0) s->xf[columnIndex]=1;
    }

    /*Update ZUB*/
    costs=0.0f;
    ilist_start_iteration(s->availCols);
    while(ilist_iterate(s->availCols,&columnIndex)) {
        if (s->xf[columnIndex]==1) costs+=scp_view_get_cost(s->problemView,columnIndex);
    }

    lagrangesolver_update_zub(s,costs);
    /*Done*/
}

void lagrangesolver_ha_reduced_costs_b(LagrangeSolver* s,int maxCandidates,unsigned char modifiedCost) {

     /*NOTE: Heuristics #4,#5
     *To complete primal (and possibly non-feasible solution),
     *maxCandidates columns are considered. The candidate
     *with lowest reduced cost(heuristic #4) or with lowest modified reduced
     *cost (heuristic #5) is selected
     *
     *Superfluous columns are removed according to their decreasing reduced cost
     *(heuristic #4) or modified reduced cost (heuristic #5)
     */


    int cols = s->problemView->columns;
    int rows = s->problemView->rows;

    SCPView* sortedView=NULL;
    
    int pci=0;
    
    int i=0;
    int j=0;
    int uri=-1;  /*Index of found uncovered row*/
    int last=-1;
    int tmp=0;
    float min;
    float tmp2;
    int minIndex;
    float costs;
    int candidateCounter;

    int columnIndex=0;
    int acl=0;
    IList* ac=NULL;

    assert(maxCandidates>0 && maxCandidates<=cols);

    memcpy(s->modifiedReducedCosts,s->reducedCosts,cols*sizeof(float));

    /*Copy the x vector*/
    memcpy(s->xf,s->x,cols);

    ac=s->availCols;
    acl=ac->length;

    while(1) {

        /*Select a row which is uncovered*/
        uri=-1;
        for(i=last+1;i<rows;i++) {
            /*Examine whether row is covered by some column*/
            tmp=0;
            ilist_start_iteration(ac);
            while(ilist_iterate(ac,&columnIndex)) {
                if (s->xf[columnIndex]==1 && scp_view_get(s->problemView,i,columnIndex)==1) {
                    tmp=1;
                    break;
                }

            }
            /*If not, set the index*/
            if (tmp==0) {
                uri=i;
                last=i;
                break;
            }
        }

        if (uri!=-1) {
            
           /*Row is uncovered. We select column that has
            *lowest reduced cost
            */
            min=POS_INFINITY;
            minIndex=-1;
            candidateCounter=0;

            ilist_start_iteration(ac);
            while(ilist_iterate(ac,&columnIndex) && candidateCounter<maxCandidates) {
            
                if (scp_view_get(s->problemView,uri,columnIndex)==1) {
                    /*Candidate found. We obtain reduced cost and check
                     *whether such cost is lowest*/
                    tmp2=s->modifiedReducedCosts[columnIndex];
                    if (tmp2<min) {
                        min=tmp2;
                        minIndex=columnIndex;
                    }
                    candidateCounter++;
                }
            }
            /*What should never happen*/
            assert(minIndex!=-1);

            /*Adding selected column to the solution*/
            s->xf[minIndex]=1;

            /*If modified cost heuristic is selected, we change current reduced cost of
             *columns that cover the recently covered row*/
            if (modifiedCost==1) {
                ilist_start_iteration(ac);
                while(ilist_iterate(ac,&columnIndex)) {
                    if (scp_view_get(s->problemView,uri,columnIndex)==1) {
                        s->modifiedReducedCosts[columnIndex]+=s->t[uri];
                    }
                }
            }

        }

        else {
            break;  /*All rows are covered now*/
        }

    }

   /*Sort columns according to their reduced costs.
    *We create a new view to the problem that contains only columns from
    *the solution. The view will be sorted according to reduced costs
    */
   sortedView= scp_view_get_column_mask_subview(s->problemView,s->xf,1);
   assert(sortedView!=NULL);
   
   quick_sort_columns(sortedView,lagrangesolver_compare_reduced_cost2,s);


    /*Now we will consider all columns in the xf. We will try to
     *remove them and test whether the solution is valid after column
     *removal*/
    for(j=sortedView->columns-1;j>=0;j--) {
        pci=sortedView->parentColumnMap[j];
        if (s->xf[pci]==0) continue;
        s->xf[pci]=0;
        if (scp_view_is_solution(s->problemView,s->xf)==0) s->xf[pci]=1;
    }

   scp_view_delete(sortedView);

    /*Update ZUB*/
    costs=0.0f;
    ilist_start_iteration(ac);
    while(ilist_iterate(ac,&columnIndex)) {
        if (s->xf[columnIndex]==1) costs+=scp_view_get_cost(s->problemView,columnIndex);
    }

    lagrangesolver_update_zub(s,costs);
    /*Done*/
    
}


int lagrangesolver_subgradient(LagrangeSolver* s) {
    
    int i=0;
    int j=0;
    
    int rows=s->problemView->rows;
    int cols=s->problemView->columns;
    
    int sum=0;
    
    for(i=0;i<rows;i++) {
        sum=0;
        for(j=0;j<cols;j++) {
            sum += s->x[j] * scp_view_get(s->problemView,i,j);
        }
        s->G[i]=1-sum;
    }
    
    /*Adjusting the subgradient*/
    for(i=0;i<rows;i++) {
        if (s->t[i]==0.0f && s->G[i]<0) s->G[i]=0;
    }
    
    /*Whether to STOP ?*/
    sum=0;
    for(i=0;i<rows;i++) {
        sum+=s->G[i]*s->G[i];
    }
    return sum;
    
    
    
}

int lagrangesolver_iteration(LagrangeSolver* s,int gqsum) {
    
    int rows=s->problemView->rows;
    int i=0;
    float T;
    
    /*Maximum iterations - STOP*/
    if (s->iterations>1000) return 0;
    
    
    /*Calculate the step*/ 
    T=s->iteration_multiplier*(1.05*s->ZUB - s->ZLB)/gqsum;
    
    /*Check the ZMAX* change*/
    if (s->sup_ZMAX!=s->ZMAX) {
        s->sup_iterations=0;
        s->sup_ZMAX=s->ZMAX;
    }
    else {
        s->sup_iterations++;
        if (s->sup_iterations>30) {
            s->sup_iterations=0;
            s->iteration_multiplier/=2; /*Half the iteration multiplier*/
            if (s->fastCancel==1) return 0;
        }
    }
    
    /*Update lagrange multipliers*/
    for(i=0;i<rows;i++) {
        if ( (s->t[i] +T * s->G[i])>0) {
            s->t[i]= T * s->G[i];
        }
        else {
            s->t[i]=0;
        }
    }
    
    s->iterations++;
    
    return 1;
}


int lagrangesolver_compare_columns(SCPView* v,int c1,int c2,void* miscData) {
    int x1,x2;

    x1=scp_view_get_cost(v,c1);
    x2=scp_view_get_cost(v,c2);

    if (x1<x2) return -1; else if (x1>x2) return +1;

    x1=scp_view_get_covered_by_column(v,c1);
    x2=scp_view_get_covered_by_column(v,c2);

    if (x1>x2) return -1; else if (x2>x1) return +1;
    return 0;
    
}

int lagrangesolver_compare_rows(SCPView* v,int r1,int r2,void* miscData) {

    int x1,x2;

    x1=scp_view_get_columns_covering(v,r1);
    x2=scp_view_get_columns_covering(v,r2);

    if (x1<x2) return -1; else if (x1>x2) return +1;
    return 0;
}


void lagrangesolver_sort(LagrangeSolver* s) {
    
    /*Sort columns. Cost is increasing, if the cost is equal, column that covers
     *more rows is preffered*/
    quick_sort_columns(s->problemView,lagrangesolver_compare_columns,(void*)NULL);
    
    /*Sort rows. Rows covered by less columns are first*/
    quick_sort_rows(s->problemView,lagrangesolver_compare_rows,NULL);
    
}


void lagrangesolver_removecolumns(LagrangeSolver* s) {
    
    
    int j=0;
    float cred=0.0f;
    int columnIndex=0;

    /*For each column*/
    ilist_start_iteration(s->availCols);
    while(ilist_iterate(s->availCols,&columnIndex)) {

        /*If not present*/
        if (s->x[columnIndex]==0) {
            cred=s->reducedCosts[columnIndex];
            if (s->p[columnIndex] < s->ZLB+cred) s->p[columnIndex]=s->ZLB+cred;
        }
        /*If present*/
        else {
            if (s->p[columnIndex] < s->ZLB) s->p[columnIndex]=s->ZLB;
        }
    }

    /*Removing columns that can not improve the solution*/
    j=0;
    while(j<s->availCols->length) {
        columnIndex=ilist_get(s->availCols,j);
        if (s->p[columnIndex]>s->ZUB) {
            ilist_remove(s->availCols,j);
            s->xf[columnIndex]=0;
            s->xbest[columnIndex]=0;
            s->x[columnIndex]=0;
        }
        else {
            j++;
        }
    }
    
    
}

float lagrangesolver_get_reduced_cost(LagrangeSolver* s,int columnIndex) {

    int i=0;
    int r=0;
    float sum=0.0f;

    float cred=scp_view_get_cost(s->problemView,columnIndex);
    r=s->problemView->rows;

    for(i=0;i<r;i++) {
        sum+=s->t[i]*scp_view_get(s->problemView,i,columnIndex);
    }

    cred-=sum;

    return cred;
    
}

int lagrangesolver_compare_reduced_cost(SCPView* v,int c1,int c2,void* miscData) {

    LagrangeSolver* lgs = (LagrangeSolver*)miscData;

    float x1=lgs->reducedCosts[v->parentColumnMap[c1]];
    float x2=lgs->reducedCosts[v->parentColumnMap[c2]];

    if (x1<x2) return -1; else if (x1>x2) return +1;
    return 0;
}

int lagrangesolver_compare_reduced_cost2(SCPView* v,int c1,int c2,void* miscData) {

    LagrangeSolver* lgs = (LagrangeSolver*)miscData;

    float x1=lgs->modifiedReducedCosts[v->parentColumnMap[c1]];
    float x2=lgs->modifiedReducedCosts[v->parentColumnMap[c2]];

    if (x1<x2) return -1; else if (x1>x2) return +1;
    return 0;
}

void lagrangesolver_update_zub(LagrangeSolver* s,float candZUB) {

    /*If proposed ZUB is lower than original*/
    if (candZUB<s->ZUB) {
        s->ZUB=candZUB;
        /*Update best solution found*/
        memcpy(s->xbest,s->xf,s->problemView->columns);
    }
    /*Done*/
}
    


void lagrangesolver_delete(LagrangeSolver* s) {

    /*Check parameters and conditions*/
    if (s==NULL) return;

    if (s->G!=NULL) free(s->G);
    if (s->p!=NULL) free(s->p);
    if (s->t!=NULL) free(s->t);
    if (s->x!=NULL) free(s->x);
    if (s->xf!=NULL) free(s->xf);
    if (s->xbest!=NULL) free(s->xbest);
    if (s->reducedCosts!=NULL) free(s->reducedCosts);
    if (s->modifiedReducedCosts!=NULL) free(s->modifiedReducedCosts);
    if (s->availCols!=NULL) ilist_delete(s->availCols);

    free(s);
}

void lagrangesolver_print(LagrangeSolver* s) {
    
    int c = s->problemView->columns;
    int r = s->problemView->rows;
    
    int i=0;
    
    if (s==NULL) {
        printf("[NULL] LagrangeSolver");
        return;
    }
    
    /*Basic*/
    printf("LagrangeSolver:\n");
    printf("ZMAX:%f\nZUB:%f\nZLB:%f\n\n",s->ZMAX,s->ZUB,s->ZLB);
    
    /*Solution*/
    printf("x[]:");
    for(i=0;i<c;i++) {
        printf("%d ",s->x[i]);
    }
    printf("\n");

    /*Best feasible solution*/
    printf("xf[]:");
    for(i=0;i<c;i++) {
        printf("%d ",s->xf[i]);
    }
    printf("\n");
    
    /*columnMask*/
    printf("avcls []:\n");
    ilist_print(s->availCols);
    
    printf("\n");
    /*Pk*/
    printf("p[]:");
    for(i=0;i<c;i++) {
        printf("%f ",s->p[i]);
    }
    printf("\n");
    /*Multipliers*/
    printf("t[]:");
    for(i=0;i<r;i++) {
        printf("%f ",s->t[i]);
    }


    printf("\n");
    /*RC*/
    printf("RC[]:");
    for(i=0;i<c;i++) {
        printf("%f ",s->reducedCosts[i]);
    }


    printf("\n");
    printf("iterations: %d\n\n",s->iterations);
    
    
}

