//explicatie
//relatia solutiei se poate scrie
//sol(n)=a*sol(n-1)+a*sol(n-2)+a*sol(n-3)
//ce se poate scrie matricial
// |sol(n) | |a b c | |sol(n-1) | |sol(n-1) |
// |sol(n-1) | = |0 1 0 | x |sol(n-2) | = M x |sol(n-2) |
// |sol(n-2) | |0 0 1 | |sol(n-3) | |sol(n-3) |
//deci
// |sol(n) | |sol(n-1) | |sol(n-2) | |sol(n-3) |
// |sol(n-1) | = M x |sol(n-2) | = M^2 x |sol(n-3) |= M^3 x |sol(n-4) |......
// |sol(n-2) | |sol(n-3) | |sol(n-4) | |sol(n-5) |
//deci rezulta
// |sol(n) | |sol(2) |
// |sol(n-1) | = M^(k-2) x |sol(1) |
// |sol(n-2) | |sol(0) |
//notam cu S = M^(k-2) deci rezulta
// |sol(n) | |sol(2) |
// |sol(n-1) | = S X |sol(1) |
// |sol(n-2) | |sol(0) |
//deci sol(n)= S[1][1]*sol(2) + s[1][2]*sol(1) +S[1][3]*sol(0)
//calculul matricii S se face cu exponentiere logarirmica deoarece
//k este mare
#include <fstream>
#define Max 4
#define MOD 666013
using namespace std;
ifstream fi("msuma.in");
ofstream fo("msuma.out");
long long M[Max][Max],B[Max][Max],C[Max][Max],S[Max][Max];
long long T,i,j,m,p,q,mc,nc;
long long x,y,z,a,b,c,n;
//C=A x B
//face produsul matricilor patratice A x B cu rezultatul in C ( n X n)
void Mprodus(long long A[Max][Max],long long B[Max][Max],long long C[Max][Max],long long n)
{
long long i,j,k,x;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
x=0;
for(k=1; k<=n; k++)
x+=A[i][k]*B[k][j];
C[i][j]=x%MOD;
}
}
//A=B;
//copiaza matrice B in A (A=B;)
void Mcopy(long long A[Max][Max],long long B[Max][Max],long n)
{
long long i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
A[i][j]=B[i][j]%MOD;
}
int main()
{
fi>>T;
for(int t=1; t<=T; t++)
{
fi>>x>>y>>z>>a>>b>>c>>n;
if(n==0){ fo<<x; return 0; }
if(n==1){ fo<<y; return 0; }
if(n==2) { fo<<z; return 0; }
if(n>=3)
{
//mat sol se pune pe matricea unitate
for(i=1; i<=3; i++)
for(j=1; j<=3; j++)
if(i==j)S[i][j]=1;
else S[i][j]=0;
//facem matricea M initiala
// a b c
// 1 0 0
// 0 1 0
for(i=1; i<=3; i++)
for(j=1; j<=3; j++)
M[i][j]=0;
M[1][1]=a;M[1][2]=b;M[1][3]=c;
M[2][1]=1;
M[3][2]=1;
//exponentiere matrice a la puterea N-2
n=n-2;
while(n)//exponentiere matrice
{
if(n%2==1) { //se face S=S*M in doi pasi
Mprodus(S,M,B,3); //B=S*M
Mcopy(S,B,3); //S=B;
}
//facem M=M^2
Mcopy(B,M,3);
Mprodus(M,B,C,3);
Mcopy(M,C,3);
//
n=n/2;
}
long long sol=(S[1][1]*z+S[1][2]*y+S[1][3]*x)%MOD;
fo<<sol<<'\n';
}
}
return 0;
}
/*
#include<iostream>//100p cu un vector
using namespace std;
#define Vmax 10010
int g[Vmax], v[Vmax],best[Vmax],n, gmax;
int main() {
cin>>n>>gmax;
for (int i = 1; i <= n; i++) cin>>g[i]>>v[i];
for( int i = 1; i <= n; i++)
for( int j = gmax - g[i]; j >= 0; j--)
best[j+g[i]]=max(best[j+g[i]],best[j] + v[i]);
cout<<best[gmax];
return 0;
}*/
//*vizita 1597
//var I 40p depaseste memoria(daca fac cu doua matrici)
//pr. dinamica problema triunghi
//#include <fstream>
//#define M 300
//#define ML 10000000000000
//using namespace std;
//ifstream fi("vizita.in");
//ofstream fo("vizita.out");
//long long a[M][M],s[M][M];
//long long i,j,n,S,sol1,sol2;
//int main()
//{
// fi>>n;
// for(i=0;i<=n+1;i++) //bordare matrice pentru ca fac minim
// for(j=0;j<=n+1;j++)s[i][j]=ML;
// for(i=1;i<=n;i++)
// for(j=1;j<=i;j++)fi>>a[i][j];
// s[1][1]=a[1][1]; //calculez primul triunghi
// for(i=2;i<=n;i++)
// for(j=1;j<=i;j++)
// s[i][j]=a[i][j]+min(s[i-1][j],s[i][j-1]);
// sol1=s[n][n]; //salvez solutia primului triunghi
// //
// for(i=0;i<=n+1;i++)
// for(j=0;j<=n+1;j++)s[i][j]=ML;
// a[1][1]=0;
// for(i=2;i<=n;i++)
// for(j=1;j<=i;j++)fi>>a[i][j];
// s[1][1]=a[1][1]; //calculez al doilea triunghi
// for(i=2;i<=n;i++)
// for(j=1;j<=i;j++)
// s[i][j]=a[i][j]+min(s[i-1][j],s[i][j-1]);
// sol2=s[n][n]; //salvez solutia triunghi
// fo<<sol1+sol2<<endl;;
//// for(i=1;i<=n;i++){
//// for(j=1;j<=n;j++)fo<<s[i][j]<<" ";
//// fo<<endl;
//// }
// return 0;
//}
////var II 60p (cu o matrice depaseste memoria!!!)
//#include <fstream>
//#define M 501
//#define ML 10000000000000
//using namespace std;
//ifstream fi("vizita.in");
//ofstream fo("vizita.out");
//long long s[M][M],x;
//long long i,j,n,S,sol1,sol2;
//int main()
//{
// fi>>n;
// for(i=0;i<=n+1;i++)
// for(j=0;j<=n+1;j++)s[i][j]=ML;
// fi>>s[1][1];
// for(i=2;i<=n;i++)
// for(j=1;j<=i;j++)
// {
// fi>>x;
// s[i][j]=x+min(s[i-1][j],s[i][j-1]);
// }
// sol1=s[n][n];
// //
// s[1][1]=0;
// for(i=2;i<=n;i++)
// for(j=1;j<=i;j++)
// {
// fi>>x;
// s[i][j]=x+min(s[i-1][j],s[i][j-1]);
// }
// sol2=s[n][n];
// fo<<sol1+sol2<<endl;;
// return 0;
//}
//idee
//se calculeaza de doua ori separat cele 2 triunghiuri
//si apoi se aduna rezultatele sol1 si sol2
////var III 100p cu doi vectori
//#include <fstream>
//#define M 1003
//#define ML 10000000000000 //10000 de mld !!!! se pot aduna el. din triunghi si depasesc 1 mld !!!
//using namespace std;
//ifstream fi("vizita.in");
//ofstream fo("vizita.out");
//long long a[M],b[M],c[M];
//long long i,j,n,S,sol1,sol2;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)a[i]=ML;
// c[0]=ML;
// fi>>a[1];c[1]=a[1];
// //fo<<c[1]<<endl;
// for(i=2;i<=n;i++)
// {
// for(j=1;j<=i;j++)fi>>b[j]; //b vectorul citit
// for(j=1;j<=i;j++)c[j]=b[j]+min(c[j-1],a[j]);//c vectorul nou calculat
// for(j=1;j<=i;j++)a[j]=c[j]; //a vectorul vechi calculat
// }
// sol1=c[n];
// //
// for(i=1;i<=n;i++)a[i]=ML;
// c[0]=ML;
// a[1]=0;c[1]=a[1];
// for(i=2;i<=n;i++)
// {
// for(j=1;j<=i;j++)fi>>b[j];
// for(j=1;j<=i;j++)c[j]=b[j]+min(c[j-1],a[j]);
// for(j=1;j<=i;j++)a[j]=c[j];
// }
// sol2=c[n];
// fo<<sol1+sol2;
// return 0;
//}
//////idee
////iau fiecare divizor a[i] si pt. fiecare nr[j] cresc
////din a[i] in a[i] numerull de solutii cu nr[j]
//// folosesc un vector in care calculez nrr care apoi il adun la vectorul nr
////6=>1 2 3 6
//// 0 1 2 3 4 5 6
////nr 1 0 0 0 0 0 0
////nrr 0 1 1 1 1 1 1 (am pus pe 1)
////--------------------------------
////nr 1 1 1 1 1 1 1
////nrr 0 0 1 1 2 2 3(am pus pe 2)
////--------------------------------
////nr 1 1 2 2 3 3 4
////nrr 0 0 0 1 1 1 3(am pus pe 3)
////--------------------------------
////nr 1 1 2 3 4 4 7
////nrr 0 0 0 0 0 0 1(am pus pe 6)
////--------------------------------
////nr 1 1 2 3 4 4 8
//#include<iostream>
//#include<algorithm>
//#define M 123457
//using namespace std;
//int nr[10003],nrr[10003],i,j,n,a[1000],d,m,k;
//int main(){
// cin>>n;
// for(d=1;d*d<=n;d++) //determinare divizori eficient
// if(n%d==0){
// a[++m]=d;
// if(d!=n/d)a[++m]=n/d;
// }
// // for(i=1;i<=m;i++)cout<<a[i]<< " ";
// sort(a+1,a+m+1);
// nr[0]=1;
// for(i=1;i<=m;i++){
// for(j=0;j<=n-a[i];j++)
// {
// k=j; //fiecare nr[j] se aduna cu a[i],2*a[i],3*a[i]....
// while(k<=n-a[i]) //si crestem numarul de solutii pt. j+a[i] cu nr[j]
// {
// nrr[k+a[i]]+=nr[j]; //punem in noul vector nrr nole solutii
// k=k+a[i]; //sa nu ne incurcam
// }
// }
// for(j=0;j<=n;j++) //adun solutiile lui nrrla nr si pun nrr pe 0
// {nr[j]+=nrr[j];nr[j]=nr[j]%M;nrr[j]=0;}
// }
// cout<<nr[n]%M;
// //for(i=1;i<=n;i++)cout<<nr[i]<< " ";
//return 0;
//}
//////var I 100p ()
//////se noteaza capetele cu +e si -e, apoi se insumeaza
////#include <fstream>
////#define Nmax 2000002
////using namespace std;
////ifstream fi("ozn.in");
////ofstream fo("ozn.out");
////int a[Nmax];
////int i,j,n,m,k,x1,x2,y11,y2,oz,e,s;//y1 este functie pe campion!!!!
////int main()
////{
//// fi>>n>>k;
//// for(i=1;i<=n;i++)
//// {
//// fi>>x1>>y11>>x2>>y2>>e;
//// a[x1]+=e;
//// a[x2+1]-=e;
//// }
//// for(i=1;i<=2000001;i++)
//// a[i]+=a[i-1];
//// for(j=1;j<=k;j++){
//// fi>>oz;
//// fo<<a[oz]<<'\n';
//// }
//// return 0;
////}
//
//#include <cstdio>//var II 100p cu scanf
//#define Nmax 100003
//using namespace std;
//int b,maxi,ok,sol,k,y,H,W,n,i,x1[Nmax],x2[Nmax];
//int main()
//{
// freopen("lac.in","r",stdin);
// freopen("lac.out","w",stdout);
// scanf("%d%d%d",&H,&W,&n);
// for(i=1; i<=n; i++) scanf("%d%d%d",&y,&x1[i],&x2[i]);
// n++;
// x1[n]=H;
// x2[i]=H+1; //se adauga un interval imaginar
// b=0; //pt. a vedea daca se acopera intervalul[0,H]
// for(i=1; i<=n;)
// if(b>=x1[i])
// {
// if(x2[i]>maxi)maxi=x2[i];
// ok=1; //are loc o intersectie de intervale
// i++;
// }
// else if(ok==0)//nu a avut loc o intersectie de intervale
// { //deci exista intrerupere bai!!!!! nu exista solutie
// sol=-1;
// break;
// }
// else
// {
// k++; //cresc numar de intervale
// b=maxi; //se schimba intervalul curent
// maxi=0;
// ok=0;
// }
// if(sol==0)printf("%d",n-k);
// else printf("%d",0);
// return 0;
//}
//#include <fstream> //backtraking iterativ
//using namespace std;//var II 90p timpul!!!!
//ifstream fi("pluricex.in");
//ofstream fo("pluricex.out");
//int i,j,n,d,nr,t,k,x,fr[30];
//int a[30],b[30][30];
//int main()
//{
// fi>>n>>k>>d;
// for(i=1;i<=n;i++){
// fi>>nr;
// for(j=1;j<=nr;j++){fi>>t;b[i][t]=1;}
// }
// //for(i=1;i<=n;i++){ for(j=1;j<=d;j++) fo<<b[i][j]<<" "; fo<<endl; }
// i=1;//backtraking iterativ
// while(i>0){ //daca am ajuns la solutie o afisam
// if(i==k+1){
// for(j=1;j<=d;j++)fr[j]=0;
// for(j=1;j<=i-1;j++){
// x=a[j];
// for(t=1;t<=d;t++)fr[t]+=b[x][t];
// }
// //for(j=1;j<=d;j++) fo<<fr[j]<<" ";fo<<endl;
// bool sol=true;
// for(j=1;j<=d;j++)
// if(fr[j]==0)sol=false;
// if(sol){
// for(j=1;j<=i-1;j++) fo<<a[j]<<" ";
// fo<<'\n';
// }
// i--; //revenire
// }
// else //daca nu am ajuns la solutie
// if(a[i]<n){
// a[i]++; //daca se poate se creste valoarea lui a[i]
// if(a[i]>a[i-1]) { i++;a[i]=a[i-1];}// merge cu 10p mai repede!!//daca e valid de continua
// }
// else {a[i]=0;i--;} //daca nu se poate creste valoarea lui a[i] se revine
// }
// return 0;
//}
//#include <fstream> //backtraking iterativ
//using namespace std;//var I 80p timpul!!!!
//ifstream fi("pluricex.in");
//ofstream fo("pluricex.out");
//int i,j,n,d,nr,t,k,x,fr[30];
//int a[30],b[30][30];
//int main()
//{
// fi>>n>>k>>d;
// for(i=1;i<=n;i++){
// fi>>nr;
// for(j=1;j<=nr;j++){fi>>t;b[i][t]=1;}
// }
// //for(i=1;i<=n;i++){ for(j=1;j<=d;j++) fo<<b[i][j]<<" "; fo<<endl; }
// i=1;//backtraking iterativ
// while(i>0){ //daca am ajuns la solutie o afisam
// if(i==k+1){
// for(j=1;j<=d;j++)fr[j]=0;
// for(j=1;j<=i-1;j++){
// x=a[j];
// for(t=1;t<=d;t++)fr[t]+=b[x][t];
// }
// //for(j=1;j<=d;j++) fo<<fr[j]<<" ";fo<<endl;
// bool sol=true;
// for(j=1;j<=d;j++)
// if(fr[j]==0)sol=false;
// if(sol){
// for(j=1;j<=i-1;j++) fo<<a[j]<<" ";
// fo<<'\n';
// }
// i--; //revenire
// }
// else //daca nu am ajuns la solutie
// if(a[i]<n){
// a[i]++; //daca se poate se creste valoarea lui a[i]
// if(a[i]>a[i-1]) i++;//daca e valid de continua
// }
// else {a[i]=0;i--;} //daca nu se poate creste valoarea lui a[i] se revine
// }
// return 0;
//}
//generare submultimi de retete prescrise
//#include<fstream>
//#include<iomanip>
//#define M 30
//using namespace std;
//ifstream fi("reteta2.in");
//ofstream fo("reteta2.out");
//int r[M][M],pret[M],comp[M],a[M],fr[M],sol[M];
//int i,j,n,m;
//float val_reteta[M],sum_minima=10000000,s;
//void prelucreaza(int i){
// int j,ok;
// float sum=0;
// for(j=1;j<=n;j++)fr[j]=0;
// for(i=1;i<=m;i++)
// if(a[i]==1){ //facem vectorul de
// for(j=1;j<=r[i][0];j++) //frecventa pentru fiecare
// fr[r[i][j]]++; //submultime
// }
// ok=1; //verif. daca avem toate medicamentele
// for(i=1;i<=n;i++) //exact o singura data in solutie
// if(fr[i]!=1)ok=0;
// if(ok==1)
// {for(i=1;i<=m;i++)
// if(a[i]==1)sum+=val_reteta[i];
// if(sum<sum_minima){sum_minima=sum;
// for(j=1;j<=m;j++)sol[j]=a[j];}
// }
//}
//void bk(int i){
//for(int val=0;val<=1;val++)
// {
// a[i]=val;
// if(i==m)prelucreaza(i);
// else bk(i+1);
// }
//}
//int main(){
//fi>>n>>m;
//for(i=1;i<=m;i++){
// fi>>comp[i]; //tipul necompensat(1) sau compensat(2)
// fi>>r[i][0];//numar de medicamente de pe reteta
// for(j=1;j<=r[i][0];j++)fi>>r[i][j];
//}
//for(i=1;i<=n;i++)fi>>pret[i];
//for(i=1;i<=m;i++){ //se precalculeaza initial
// s=0; //pretul fiecarei retete
// for(j=1;j<=r[i][0];j++)
// s+=pret[r[i][j]];
// if(comp[i]==2)s=s/2.0;
// val_reteta[i]=s;
//}
//bk(1);
//fo<<fixed<<setprecision(1)<<(int)(sum_minima*10)/10.0;
//return 0;
//}
//{reteta2 OJI 2008 VIII 100p backtracking}
//var
//ss,s,j,t,k,n,kk,m,i,q:longint;
//a:array[1..20,1..20] of byte;
//b:array[1..20] of real;
//res:longint;
//fr,h,L,pret,c:array [1..20] of integer;
//f,g:text;
//s1,min:real;
//begin
//assign(f,'reteta2.in');
//
//reset(f);
//assign(g,'reteta2.out');;
//rewrite(g);
//read(f,n,m);
//for i :=1 to m do
//begin {c[i]=2 reteta compensata c[i]=1 reteta necompensata }
// read(f,c[i],L[i]); {L[i] - lungime(numar de medicamente in reteta i)}
// for j :=1 to L[i] do read(f,a[i,j]);
//end;
//for i :=1 to n do read(f,pret[i]);
//for i := 1 to m do
// begin
// ss:=0;
// for j:= 1 to L[i] do ss:=ss+pret[a[i,j]];
// if c[i]=2 then b[i]:=ss/2 {b[i] - pretul retetei i}
// else b[i]:=ss;
// end;
//min:=3121321;
//i:=1;
//while i>0 do
//begin
//if i=m+1 then
// begin h[i]:=0;i:=i-1;
// s1:=0;
// for j:= 1 to n do fr[j]:=0;
// for j:=1 to i do
// if h[j]=1 then s1:=s1+b[j]; {s1 - suma costurilor pt. o combinatie }
// if s1<min then
// begin
// for j:= 1 to i do
// if h[j]=1 then {fr[] - medicamentele utilizate in retete pt. o combinatie }
// for t:= 1 to L[j] do inc(fr[a[j,t]]);
// kk:=0;
// for j:= 1 to n do
// if fr[j]=1 then kk:=kk+1;
// if kk=n then min:=s1; {daca s-a folosit o singura data fiecare medicament}
// end;
// end
// else
// if h[i]<2 then
// begin
// h[i]:=h[i]+1; i:=i+1;
// end
// else begin h[i]:=0;i:=i-1; end;
//end;
//res:=trunc(min*10);
//{writeln(g,res div 10,'.',res mod 10);}
//writeln(g,min:10:1);
//close(f);
//close(g);
//end.
//60p
//idee se ordoneaza crescator si se aduna primele doua elemente
//si se pun in lista crescatoare
//(se mentine lista ordonata crescator tot timpul si aleg primele doua elemente mai mica)
//inserez elementul in o(n)
//
//#include<algorithm>
//#include <iostream>
//using namespace std;
// int n, i,j, s,ssol,x,k,t;
// int a[100003];
// int main()
//{
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i];
// sort(a+1,a+n+1);
// k=n;
// i=1;
// while(k>=2){
// k--;
// x=a[i]+a[i+1];
// s+=x;
// i++;
// a[i]=x;
// j=i;
// while(j<n and a[j]>a[j+1]){swap(a[j],a[j+1]);j++;}
// // for(t=i;t<=n;t++)cout<<a[t]<<" ";cout<<"s="<<s<<endl;
// }
// cout<<s;
// return 0;
//}
//
////60p
////idee se ordoneaza crescator si se aduna primele doua elemente
////si se pun in lista crescatoare
////(se mentine lista ordonata crescator tot timpul si aleg primele doua elemente mai mica)
////inserez elementul in O(n)
//#include<algorithm>
//#include <iostream>
//using namespace std;
// int n, i,j, s,ssol,x,k,t;
// int a[100003];
// int main()
//{
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i];
// sort(a+1,a+n+1);
// k=n;
// i=1;
// while(k>=2){ //am cel putin doua elemente(k=numarul de elemente)
// k--;
// x=a[i]+a[i+1]; //calculez suma
// s+=x;
// i++;
// a[i]=x; //pun suma la inceputul vectorului
// j=i; //interschimb elementele pana sirul devine ordonat
// while(j<n and a[j]>a[j+1]){swap(a[j],a[j+1]);j++;}
// // for(t=i;t<=n;t++)cout<<a[t]<<" ";cout<<"s="<<s<<endl;
// }
// cout<<s;
// return 0;
//}
////cautare binara cea mai mare sau egala val mai mica ca x
////intr-un sir descrescator
//#include <fstream>
//# define Max 100005
//using namespace std;
//ifstream fi("vintage.in");
//ofstream fo("vintage.out");
//int a[Max];
//int i,j,n,m,x,p;
//int cbin(int x){ //10 8( 7)
// int st,dr,mij;
//st=1;dr=m;
//while(st<=dr){
// mij=(st+dr)/2;
// if(x==a[mij])return mij;
// else
// if(x>a[mij]) dr=mij-1;
// else st=mij+1;
//}
//return st;
//}
//int main()
//{
// fi>>n;
// fi>>x;
// a[++m]=x;
// for(i=2;i<=n;i++)
// {
// for(int j=1;j<=m;j++)fo<<a[j]<<" ";
// fo<<" "<<m<<endl;
// fi>>x;
// p=cbin(x);
// if(p>m){a[++m]=x;}
// else a[p]=x;
// //cout<<p<<" "<<m<<endl;
// }
// for(int j=1;j<=m;j++)fo<<a[j]<<" ";
// fo<<" "<<m<<endl;
// fo<<m;
// return 0;
//}
////cautare binara cea mai mare sau egala val mai mica ca x
////intr-un sir descrescator
//#include <iostream>
//# define Max 100005
//using namespace std;
//int a[Max];
//int i,j,n,m,x,p;
//int cbin(int x){ //10 8( 7)
// int st,dr,mij;
//st=1;dr=m;
//while(st<=dr){
// mij=(st+dr)/2;
// if(x==a[mij])return mij;
// else
// if(x>a[mij]) dr=mij-1;
// else st=mij+1;
//}
//return st;
//}
//int main()
//{
// cin>>n;
// cin>>x;
// a[++m]=x;
// for(i=2;i<=n;i++)
// {
// cin>>x;
// p=cbin(x);
// if(p>m){a[++m]=x;}
// else a[p]=x;
// //cout<<p<<" "<<m<<endl;
// }
// cout<<m;
// return 0;
//}
//#include <iostream>
//using namespace std;
//int rest[100003],a[100003],c[100003],i,kk,n,nrc,k,j,mindif,poz;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// nrc=1;
// for(i=1;i<=n;i++)
// {
// mindif=2000001;
// poz=0;
// for(j=1;j<=nrc;j++)
// if(a[i]>c[j] and a[i]-c[j]<mindif)
// {poz=j;mindif=a[i]-c[j];}
// if(poz!=0)c[poz]=a[i]; //punem elementul in coada a.i. sa fie mai mare
// else {nrc++;c[nrc]=a[i];} //altfel se face o noua coada
// }
// cout<<nrc;
// return 0;
//}
////cautare binara val egala sau mai mare ca x
////intr-un sir descrescator
//#include <iostream>
//# define Max 100005
//using namespace std;
//int a[Max];
//int i,j,n,m,x,p;
//int cbin(int x){ //10 8( 7)
// int st,dr,mij;
//st=1;dr=m;
//while(st<=dr){
// mij=(st+dr)/2;
// if(x==a[mij])return mij;
// else
// if(x>a[mij]) dr=mij-1;
// else st=mij+1;
//}
//return st;
//}
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// {
// cin>>x;
// p=cbin(x);
// if(p>m){a[++m]=x;}
// else a[p]=x;
// for(j=1;j<=m;j++)cout<<a[j]<<" ";cout<<endl;???
// //cout<<p<<" "<<m<<endl;
// }
// cout<<m;
// return 0;
//}
////cautare binara a rezultatului
////dupa sortarea elementelor
////c binara cea mai mica valoare buna!!
//#include <fstream>
//#include<algorithm>
//# define Max 100005
//using namespace std;
//ifstream fi("conferinta.in");
//ofstream fo("conferinta.out");
//long long a[Max];
//long long n,s,p,i,x,j,poz_last,k,sum,st,dr,mij;
//int main()
//{
// fi>>n>>s>>p;
// for(i=1;i<=n;i++)fi>>a[i];
// sort(a+1,a+n+1);
// for(i=1;i<=n;i++)
// sum+=a[i];
//// for(i=1;i<=n;i++)fo<<a[i]<<" ";fo<<endl;
// st=0;dr=sum;
// while(st<dr){
// mij=(st+dr)/2;
// //caut sol pentru valoarea mij
// k=0;
// poz_last=0;
// for(j=1;j<=n;j++)
// if(poz_last+p<=j)
// if(a[j]-a[j-p+1]<=mij){poz_last=j;k++;}
// if(k>=s)dr=mij;
// else st=mij+1;
// }
// fo<<st;
// return 0;
//}
////var II sortare normala
//#include <fstream>
//using namespace std;
//ifstream fi("vintage.in");
//ofstream fo("vintage.out");
//struct masina
//{
// int nr;
// int cost;
// int val_colectie;
//};
//masina a[1001];
//int n,i,j,k,val,cost;
//int main()
//{
// fi>>n>>k;
// for(i=1;i<=n;i++)
// {
// fi>>a[i].cost>>a[i].val_colectie;
// a[i].nr=i;
// }
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// if (a[i].val_colectie<a[j].val_colectie or
// a[i].val_colectie==a[j].val_colectie and a[i].cost>a[j].cost)
// swap(a[i],a[j]);
// //for(i=1;i<=n;i++) fo<<a[i].cost<<" "<<a[i].val_colectie<<endl;
// for(i=1;i<=k;i++)
// {
// val+=a[i].val_colectie;
// cost+=a[i].cost;
// }
// fo << val << " " << cost << '\n';
// for(i=1;i<=k;i++)
// fo<<a[i].nr<<" ";
// return 0;
//}
//var I cu sort()
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream fi("vintage.in");
//ofstream fo("vintage.out");
//struct masina
//{
// int nr;
// int cost;
// int val_colectie;
//};
//masina a[1001];
//int n,i,j,k,val,cost;
//
//bool cmp(masina x, masina y)
//{
// if (x.val_colectie>y.val_colectie)return 1;
// if (x.val_colectie==y.val_colectie and x.cost<y.cost)return 1;
// return 0;
//}
//
//int main()
//{
// fi>>n>>k;
// for(i=1;i<=n;i++)
// {
// fi>>a[i].cost>>a[i].val_colectie;
// a[i].nr=i;
// }
// sort(a+1,a+n+1,cmp);
// //for(i=1;i<=n;i++) fo<<a[i].cost<<" "<<a[i].val_colectie<<endl;
// for(i=1;i<=k;i++)
// {
// val+=a[i].val_colectie;
// cost+=a[i].cost;
// }
// fo << val << " " << cost << '\n';
// for(i=1;i<=k;i++)
// fo<<a[i].nr<<" ";
// return 0;
//}
//
//#include<fstream>
//#define M 100
//using namespace std;
//ifstream f("efort.in");
//ofstream g("efort.out");
//int b[1002],a[1002],k,s,i,j,n,ef,sb[1002];
//int main()
//{
// f>>n>>k;
// for(i=1;i<=n;i++)f>>a[i];
// b[1]=2;b[2]=3;
// for(i=3;i<=M;i++)b[i]=b[i-1]+b[i-2];
// for(i=1;i<=M;i++)sb[i]=sb[i-1]+b[i];;
// s=0;
// for(i=1;i<=n;i++){
// if(s<k)s+=a[i];
// else {ef+=k+sb[s-k];s=a[i];}
// }
// if(s<k)ef+=s;
// else ef+=k+sb[s-k];
// g<<ef<<'\n';
// f.close();g.close();
// return 0;
//}
//
//#include <fstream> //backtraking iterativ
//#include <cstring>
//#include<algorithm>
//using namespace std;
//ifstream fi("anagrame1.in");
//ofstream fo("anagrame1.out");
//int ok,i,j,n,a[100];
//char cuv[100];
//int main()
//{
// fi>>cuv;
// n=strlen(cuv);
// sort(cuv,cuv+n);
// //fo<<cuv<<endl;
// i=1;
// while(i>0){
// if(i==n+1){ //daca am ajuns la solutie o afisam
// for(j=1;j<=i-1;j++)fo<<cuv[a[j]-1];
// fo<<'\n';
// i--; //revenire
// }
// else //daca nu am ajuns la solutie
// if(a[i]<n){
// a[i]++; //daca se poate se creste valoarea lui a[i]
// ok=1;
// for(j=1;j<i;j++)
// if(a[i]==a[j])ok=0;
// if(ok==1)i++;//daca e valid de continua
// }
// else {a[i]=0;i--;}//daca nu se poate creste valoarea lui a[i] se revine
// }
// return 0;
//}
//#include <iostream>
//#include<iomanip>
//#include<cmath>
//using namespace std;
//long long i,n;;
//double x,s,r;
//int main()
//{
// cin>>n;
// cout<<n;
// return 0;
//}
//#include <iostream>
//using namespace std;
//int ha,hb,d,x;
//int main()
//{
// cin>>ha>>hb>>d;
// x=(d*d+hb*hb-ha*ha)/(2*d);
// if(ha>hb)cout<<x;
// else cout<<d-x;
// return 0;
//}
//////t=d/v(m/(km/h))=(d)/(v*1000/3600)=(d*3600)/(v*1000)(secunde)
//////t=t*60 in minute
////#include <iostream>
////using namespace std;
////long long tsec,tmin;
////double v,d;
////int main()
////{
//// cin>>v>>d;
//// tsec=(d*3600)/(v*1000);
//// if(tsec%60!=0)tmin=tsec/60+1;
//// else tmin=tsec/60;
//// cout<<tmin;
////}
//
//#include <fstream>
//using namespace std;
//ifstream fi("planta.in");
//ofstream fo("planta.out");
//long long d,a,b,n,lun,k;
//int main()
//{
// fi>>d>>a>>b>>n;
// k=n/2;
// lun=d+k*(a-b);
// if(n%2==1)lun+=a;
// fo<<lun;
// return 0;
//}
bodnariuc danut danutbod