//Grzegorz Wierzowiecki 2005
//Generuje graf z danymi takimi jakie ma rozw. kamienie.cpp
#include <stdio.h>

//dla dodatkowych informacjii o działaniu programu
//#define DEB

#define MAX(a,b)  ( (a>b) ? (a) : (b) )
#define MIN(a,b)  ( (a<b) ? (a) : (b) )

typedef unsigned long int ULI;

int main(){
	ULI i,j,n,diff; //i numer kamiania z lewej , j numer kamienia z prawej
	ULI *k; //tablica kamieni
	ULI **t; //tablica przypadków
	//rozpatruje w niej tylo ile ja moge wygrać , bo i tak na końcu suma wygranych mojej i przecinika zawsze bedzie taka sama => wygrane się dopełniają
	ULI first;

	scanf("%lu", &n);
	k = new ULI[n];
	for(i=0; i<n; ++i) scanf("%lu", &( k[i] ) );
	//printf("Kto zaczyna? (0-algorytm 1-Ty): ");
	scanf("%lu", &first);

	//inicjujemy tylko trójkąt dla oszczedzenia pamięci
	// t[ numer lewego kamienia ][ number prawego kamienia ] = ile mozna wygrać
	t = new ULI*[n];
	for(i=0; i<n; ++i){
		t[i] = new ULI[ n-i ];
		t[i] -= i;
	}
	
	printf("digraph kamienie{\n");
	printf("graph [ label=\"Drzewo przypadkow. - Grzegorz Wierzowiecki 2005 \" ];\n\n");

	//Rozpatrzenie wszystkich przypadkow ze spamiętywaniem
	//Zaczynamy od tych dla kotórych j-i=0 i dochodzimy do poczatkowego j-i=(n-1)
	for(diff=0, i=0; i< n; ++i){
		j = i ; //prawy kamien dla czyelnosci
		if( diff == first ){ //Algola ruch
			t[i][j] = k[i]; //zyskuje ten kamien
		} else {  //przeciwnika
			t[i][j] = 0; //nie zyskuje nic bo przeciwnik zabiera kamien
		}
		printf("i%luj%lu [ label=\"%lu\" , fillcolor=%s, style=filled ];\n", i ,j, t[i][j], 
				((diff%2)==first) ? "white" : "gray" );
	}
	for(diff=1; diff<n; ++diff){ //diff od difference, czyli różnica
		for(i=0; i< (n-diff); ++i){
			j = i + diff; //dla czytelności prawa strona
			if( (diff%2) == first ){ //Teraz Algola ruch
				//tyle ile moge zyskać od teraz (w najgorszym razie)
				//to wartosc kamienia ktory zabieram + to co dalej moge zyskać
				t[i][j] = MAX( t[i+1][j] + k[i], t[i][j-1] + k[j] );
			} else { //teraz Przeciwnika
				//Przeciwnik wybiera dla mnie gorszy wariant
				t[i][j] = MIN( t[i+1][j], t[i][j-1] );
			}
			printf("i%luj%lu [ label=\"%lu\" , fillcolor=%s, style=filled ];\n", i ,j, t[i][j], 
					((diff%2)==first) ? "white" : "gray" );
		}
	}
	
	for(i=0; i<n; ++i) for(j=i; j<n; ++j)
		if( i < j){
			if( (((j-i)%2) == first) ){
				printf("i%luj%lu -> i%luj%lu [ label=\"%lu\" ];\n", i,j, i+1 ,j, k[i] );
				printf("i%luj%lu -> i%luj%lu [ label=\"%lu\" ];\n", i,j, i ,j-1, k[j] );
			} else {
				printf("i%luj%lu -> i%luj%lu ;\n", i,j, i+1 ,j );
				printf("i%luj%lu -> i%luj%lu ;\n", i,j, i ,j-1);
			}
		}

	printf("}\n");
		
	return 0;
}