uva_10603_Fill

/*
 Author                             :     unlucky_13
 Problem_link                       :
 Category                           :
 Algorithm_Used                     :
 */

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define LL long long int
const long long int inf = 2147483647 ;
//const int minx=;
const int maxn=202;
using namespace std;
int a,b,c,d,D,diff,P;
bool seen[maxn][maxn][maxn] ;

void answer(int M,int A,int B,int C) // poured water resulted water amounts of A,B,C
{
    //cout<<A<<" "<<B<<" "<<C<<endl ;
    //if(P<M) return  ; //we can not yeld a better solution
    if(A<=d && (d-A)<(diff)) { diff = d-A ; P = M  ;}
    if(B<=d && (d-B)<(diff)) { diff = d-B ; P = M  ;}
    if(C<=d && (d-C)<(diff)) { diff = d-C ; P = M ; }

    //cout<<P<<endl  ;

}

struct state{
    int a,b,c,pour ;
};

int main() {

    freopen("C:\\Users\\Mazhar\\Desktop\\Text_Files\\in.txt", "r", stdin);

    int tc ;
    queue<state>q ;
    state Q ;
    scanf("%d",&tc) ;
    while(tc--)
    {
        diff = P = inf ;
        memset(seen,0,sizeof(seen)) ;
        scanf("%d %d %d %d",&a,&b,&c,&d) ;
        Q.a = Q.b = Q.pour = 0  ;
        Q.c = c ;
        seen[0][0][c] = 1 ;
        q.push(Q) ;
        while(!q.empty())
        {
            Q = q.front() ;
            q.pop() ;
            int A = Q.a ;
            int B = Q.b ;
            int C = Q.c ;
            int pour = Q.pour ;
            if(diff==0) {
                while(!q.empty()) q.pop() ;
                //P = Q.pour ;
                break ;
            }
            int AA ,BB,CC ;
            //cout<<A<<" "<<B<<" "<<C<<Q.pour<<endl ;
            //a->b

            BB = B+A ;
            AA  = 0 ;
            CC = C ;
            if(BB>b) { //B is overflowed
                AA = BB-b ;
                BB = b ;

            }

            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+(BB-B) ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;

            }
            //b->a
            AA = B+A ;
            BB = 0 ;
            CC = C ;
            if(AA>a) { //A is overflowed
                BB = AA-a ;
                AA = a ;

            }
            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+(AA-A) ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;


            }
            //b->c
            CC = C+B ;
            BB = 0 ;
            AA = A ;
            if(CC>c) { //C is overflowed
                BB = CC-c ;
                CC = c ;
            }

            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+(CC-C) ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;

            }
            //c->b
            BB = B+C ;
            CC = 0 ;
            AA = A ;
            if(BB>b){
                CC = BB-b ;
                BB = b ;
            }

            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+BB-B ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;
            }
            //a->c
            CC = A+C ;
            AA = 0 ;
            BB = B ;
            if(CC>c){
                AA = CC-c ;
                CC = c ;
            }
            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+CC-C ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;
            }
            //c->a
            AA = C+A ;
            CC =  0 ;
            BB = B ;
            if(AA>a){
                CC = AA-a ;
                AA = a ;
            }
            if(seen[AA][BB][CC]==0)
            {
                seen[AA][BB][CC]= 1 ;
                Q.a = AA ;
                Q.b = BB ;
                Q.c = CC ;
                Q.pour = pour+AA-A ;
                q.push(Q) ;
                answer(Q.pour,AA,BB,CC) ;
            }





        }
       // cout<<diff<<endl ;
        cout<<P<<" "<<d-diff<<endl ;

    }

    return 0;

}