import java.util.*;
class SPM
{
	int i,j,k,l,m,n;
	public void Mat()
	{

		System.out.println("Enter the no. of Productions:\t");
		Scanner Sc2=new Scanner(System.in);
		m=Sc2.nextInt();
		String[] prod=new String[m];
		System.out.println("\nEnter the Productions:\t");
		Scanner Sc3= new Scanner(System.in);
		for(i=0;i<m;i++)
		{
			prod[i]=Sc3.nextLine();
		}

		System.out.println("\nEnter the total No of Terminals and Non Terminals:");
		Scanner sc=new Scanner(System.in);
		k=sc.nextInt();
		String[] Str= new String[k];
		Scanner Sc1=new Scanner(System.in);
		System.out.println("Enter Non Terminals & Terminals:\t");
		for(i=0;i<k;i++)
		{
			Str[i]=Sc1.nextLine();
		}

		System.out.println("\nProductions:\t");
		for(i=0;i<m;i++)
		{
			System.out.println(prod[i]);
		}

		//Ist Matrix
		int[][] Ist=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				for(n=0;n<m;n++)
				{
					if((Str[i].charAt(0)==prod[n].charAt(0)) && (Str[j].charAt(0)==prod[n].charAt(3)))
					{
						Ist[i][j]=1;
					}
					else{}
				}

			}
		}
		System.out.println("\nFirst Matrix-\n");
		Printer(Ist,Str);

		//Ist+ matrix
		int[][] IstPlus=new int[k][k];
				for(i=0;i<k;i++)
				{
					for(j=0;j<k;j++)
					{
						IstPlus[i][j]=Ist[i][j];
					}
				}

				for(i=0;i<k;i++)
				{
					for(j=0;j<k;j++)
					{
						if(IstPlus[j][i]==1)
						{
							for(n=1;n<k;n++)
							{
								IstPlus[j][n] = IstPlus[j][n] | IstPlus[i][n];
							}
						}
					}
				}
				System.out.println("\nfirst+ matrix-\n");
				Printer(IstPlus,Str);

		//Ist*
		int[][] IstStar=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				IstStar[i][j]=IstPlus[i][j];
				if(i==j)
					IstStar[i][j]=1;
			}
		}
		System.out.println("\nFirst Matrix-\n");
		Printer(IstStar,Str);

		//Last
		int[][] Last=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=1;j<k;j++)
			{
				for(n=0;n<m;n++)
				{
					if(prod[n].length()==4)
					{
						if((Str[i].charAt(0)==prod[n].charAt(0)) && (Str[j].charAt(0)==prod[n].charAt(3)))
							Last[i][j]=1;
					}
					if(prod[n].length()==5)
					{
						if((Str[i].charAt(0)==prod[n].charAt(0)) && (Str[j].charAt(0)==prod[n].charAt(4)))
							Last[i][j]=1;
					}
					if(prod[n].length()==6)
					{
						if((Str[i].charAt(0)==prod[n].charAt(0)) && (Str[j].charAt(0)==prod[n].charAt(5)))
							Last[i][j]=1;
					}
				}
			}
		}
		System.out.println("\nLast matrix-\n");
		Printer(Last,Str);

		//Last+
		int[][] LastPlus=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				LastPlus[i][j]=Last[i][j];
			}
		}

		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				if(LastPlus[j][i]==1)
				{
					for(n=1;n<k;n++)
					{
						LastPlus[j][n] = LastPlus[j][n] | LastPlus[i][n];
					}
				}
			}
		}
		System.out.println("\nLast+ matrix-\n");
		Printer(LastPlus,Str);

		//last* matrix
		int[][] LastStar=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				LastStar[i][j]=LastPlus[i][j];
				if(i==j)
				LastStar[i][j]=1;
			}
		}
		System.out.println("\nLast* matrix-:\n");
		Printer(LastStar,Str);

		//Equal matrix
		int[][] Equal=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				for(n=0;n<m;n++)
				{
					if(prod[n].length()==6)
					{
						if(prod[n].charAt(3)==Str[i].charAt(0) && prod[n].charAt(4)==Str[j].charAt(0))
						Equal[i][j]=1;
						if(prod[n].charAt(4)==Str[i].charAt(0) && prod[n].charAt(5)==Str[j].charAt(0))
						Equal[i][j]=1;
					}
					if(prod[n].length()==5)
					{
						if(prod[n].charAt(3)==Str[i].charAt(0) && prod[n].charAt(4)==Str[j].charAt(0))
						Equal[i][j]=1;
					}
				}
			}
		}
		System.out.println("\nEqual matrix-\n");
		Printer(Equal,Str);

		//Less than matrix
		int[][] Less=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				for(n=01;n<k;n++)
				{
					Less[i][j] = Less[i][j] | (Equal[i][n] * IstPlus[n][j]);
				}
			}
		}
		System.out.println("\nLess than matrix-\n");
		Printer(Less,Str);

		//Greater than matrix
		int[][] LastPT=new int[k][k];
		int[][] Great=new int[k][k];
		String[][] GreatSym=new String[k][k];
		int[][] Great1=new int[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				LastPT[i][j]=LastPlus[j][i];
			}
		}
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				for(n=0;n<k;n++)
				{
					Great1[i][j]=Great1[i][j]|(LastPT[i][n]*Equal[n][j]);
				}
			}
		}
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				for(n=0;n<k;n++)
				{
					Great[i][j]=Great[i][j]|(Great1[i][n]*IstStar[n][j]);
				}
			}
		}
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				if(Great[i][j]==1)
				GreatSym[i][j]=">";
				else
				GreatSym[i][j]="0";
			}
		}
		System.out.println("\nGreater than matrix-\n");
		Printer(GreatSym,Str);

		//SPM matrix
		String[][] SPMat=new String[k][k];
		for(i=0;i<k;i++)
		{
			for(j=0;j<k;j++)
			{
				if(Equal[i][j]==1)
				SPMat[i][j]="=";
				else if(Less[i][j]==1)
				SPMat[i][j]="<";
				else if(Great[i][j]==1)
				SPMat[i][j]=">";
				else
				SPMat[i][j]="0";
			}
		}
		System.out.println("\nSPM matrix-\n");
		Printer(SPMat,Str);
	}
	public void Printer(int[][] f,String[] s)
	{
System.out.print("     ");
		for(j=0;j<k;j++)
		{
			if(s[j]!=null)
			System.out.print(s[j] + "    ");
			else
			System.out.print("     ");
		}
		for(i=0;i<k;i++)
		{
			System.out.print("\n" + s[i]);
			for(j=0;j<k;j++)
			{
				System.out.print("    " + f[i][j]);
			}
		}
	}
	public void Printer(String[][] f,String[] s)
	{

System.out.print("     ");
	for(j=0;j<k;j++)
		{
			if(s[j]!=null)
			System.out.print(s[j] + "    ");
			else
			System.out.print("     ");
		}
		for(i=0;i<k;i++)
		{
			System.out.print("\n" + s[i]);
			for(j=0;j<k;j++)
			{
				System.out.print("    " + f[i][j]);
			}
		}
	}




}

public class SPMatrix
{
	public static void main(String args[])
	{
		SPM SPMat=new SPM();
		SPMat.Mat();
	}


}