import java.io.*;
import java.util.*;

class OPMatrix
{
	int i,j,k,z,w,q,p,l,y;
	String[] s;
	public void Matrix()
	{
		System.out.println(" Enter the number of Non-terminals & terminals:\t");
		Scanner c = new Scanner(System.in);
		k=c.nextInt();
		s = new String[k+1];
		int[][] first = new int[k+1][k+1];
		int[][] firstplus = new int[k+1][k+1];
		int[][] firststar = new int[k+1][k+1];
		int[][] firstterm = new int[k+1][k+1];
		int[][] last = new int[k+1][k+1];
		int[][] lastplus = new int[k+1][k+1];
		int[][] laststar = new int[k+1][k+1];
		int[][] lastterm = new int[k+1][k+1];
		int[][] temptrans = new int[k+1][k+1];
		int[][] equal = new int[k+1][k+1];
		int[][] less = new int[k+1][k+1];
		int[][] temp = new int[k+1][k+1];
		int[][] great1 = new int[k+1][k+1];
		int[][] great = new int[k+1][k+1];
		int[][] equalp =new int[k+1][k+1];
		String[][] opm = new String[k+1][k+1];
		String str="";
		String T = "+*()i";
		String NT="ETF";
		String symbols=" ";
		Scanner b = new Scanner(System.in);
		System.out.println(" Enter the " + k + " Non-terminals & terminals:\t");
		for(i=1;i<k+1;i++)
		{
			s[i]=b.nextLine();
			symbols+=s[i];
		}
		System.out.println("\n Enter the number of productions:\t");
		Scanner x = new Scanner(System.in);
		z=x.nextInt();

		String[] prod = new String[z];
		System.out.println("Enter the " + z + " productions:\t");
		Scanner d = new Scanner(System.in);
		for(i=0;i<z;i++)
		{
			prod[i]=d.nextLine();
		}
		System.out.println("\n The productions are:\t");
		for(i=0;i<z;i++)
		{
			System.out.println(prod[i]);
		}
		//First matrix
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=0;w<z;w++)
				{
					if((s[i].charAt(0)==prod[w].charAt(0)) && (s[j].charAt(0)==prod[w].charAt(4)))
						first[i][j]=1;
				}
			}
		}
		System.out.println("\n The First matrix is:\n");
		Printer(first,s);
		//First plus matrix
		System.out.println(" ");
		System.out.println("\n The First+ matrix is:\n");
		firstplus=Warshall(first);
		//First star matrix
		System.out.println(" ");
		System.out.println("\n The First* matrix is:\n");
		firststar=Kleens(firstplus);
		//First Term matrix
		System.out.println(" ");
		System.out.println("\n The First term matrix is:\n");
		for(i=0;i<prod.length;i++)
		{
			for(j=0;j<T.length();j++)
			{
				for(p=0;p<NT.length();p++)
				{
					if((prod[i].length()-1==4)&&prod[i].charAt(4)==T.charAt(j))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(4));
						firstterm[l][y]=1;
					}
					if((prod[i].length()-1>4)&&(prod[i].charAt(5)==T.charAt(j)))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(5));
						firstterm[l][y]=1;
					}
					if((prod[i].length()-1>4)&&(prod[i].charAt(5)==NT.charAt(p)))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(4));
						firstterm[l][y]=1;
					}
				}
			}
		}
		Printer(firstterm,s);
		//Last Matrix
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=0;w<z;w++)
				{
					if(prod[w].length()==5)
					{
						if((s[i].charAt(0)==prod[w].charAt(0)) && (s[j].charAt(0)==prod[w].charAt(4)))
							last[i][j]=1;
					}
					if(prod[w].length()==6)
					{
						if((s[i].charAt(0)==prod[w].charAt(0)) && (s[j].charAt(0)==prod[w].charAt(5)))
							last[i][j]=1;
					}
					if(prod[w].length()==7)
					{
						if((s[i].charAt(0)==prod[w].charAt(0)) && (s[j].charAt(0)==prod[w].charAt(6)))
							last[i][j]=1;
					}
				}
			}
		}
		System.out.println("\n The Last matrix is:\n");
		Printer(last,s);
		//Last+ matrix
		System.out.println(" ");
		System.out.println("\n The Last+ matrix is:\n");
		lastplus=Warshall(last);
		//Last* Matrix
		System.out.println(" ");
		System.out.println("\n The Last* matrix is:\n");
		laststar=Kleens(lastplus);
		//Last Term matrix
		System.out.println(" ");
		System.out.println("\n The Last term matrix is:\n");
		for(i=0;i<prod.length;i++)
		{
			for(j=0;j<T.length();j++)
			{
				for(p=0;p<NT.length();p++)
				{
					if((prod[i].length()-1==4) && prod[i].charAt(4)==T.charAt(j))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(4));
						lastterm[l][y]=1;
					}
					if((prod[i].length()-1>4) && (prod[i].charAt(5)==T.charAt(j)))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(5));
						lastterm[l][y]=1;
					}
					if((prod[i].length()-1>4) && (prod[i].charAt(5)==NT.charAt(p)))
					{
						l=symbols.indexOf(prod[i].charAt(0));
						y=symbols.indexOf(prod[i].charAt(6));
						lastterm[l][y]=1;
					}
				}

			}
		}
		Printer(lastterm,s);
		//Equal matrix
		for(i=0;i<z;i++)
		{
			if(prod[i].substring(4).length()>=2)
			{
				str=prod[i].substring(4);
				for(j=0;j<str.length()-1;j++)
				{
					l=symbols.indexOf(str.charAt(j));
					y=symbols.indexOf(str.charAt(j+1));
					equal[l][y]=1;
				}
			}
		}
		System.out.println("\n The Equal matrix is:\n");
		Printer(equal,s);
		//Equal Precedence matrix
		for(i=0;i<z;i++)
		{
			for(j=0;j<T.length();j++)
			{
				for(p=0;p<NT.length();p++)
				{
					for(w=0;w<T.length();w++)
					{
						if((prod[i].substring(4)).equals(T.substring(j, j+1) + NT.substring(p, p+1) + T.substring(w, w+1)))
						{
							l=symbols.indexOf(prod[i].charAt(4));
							y=symbols.indexOf(prod[i].charAt(6));
							equalp[l][y]=1;
						}
					}
				}
			}
		}
		System.out.println("\n The Equal Precedence matrix is:\n");
		Printer(equalp,s);
		//Less than matrix
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=1;w<k+1;w++)
				{
					temp[i][j] = temp[i][j] | (equal[i][w] * firststar[w][j]);
				}
			}
		}
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=1;w<k+1;w++)
				{
					less[i][j] = less[i][j] | (temp[i][w] * firstterm[w][j]);
				}
			}
		}
		System.out.println("\n The Less than matrix is:\n");
		Printer(less,s);
		//Greater than matrix
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				temp[i][j]=0;
				for(w=1;w<k+1;w++)
				{
					temp[i][j]=temp[i][j]|(laststar[i][w]*lastterm[w][j]);
				}
			}
		}
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				temptrans[j][i]=temp[i][j];
			}
		}
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=1;w<k+1;w++)
				{
					great[i][j]=great[i][j]|(temptrans[i][w]*equal[w][j]);
				}
			}
		}
		System.out.println("\n The Greater than matrix is:\n");
		Printer(great,s);
		//OPM matrix
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				if(equalp[i][j]==1)
					opm[i][j]="=";
				else if(less[i][j]==1)
					opm[i][j]="<";
				else if(great[i][j]==1)
					opm[i][j]=">";
				else
					opm[i][j]="0";
			}
		}
		System.out.println("\n The opm matrix is:\n");
		Printer(opm,s);
		System.out.println("\n The opm matrix after superimposing is:\n");

		for(j=4;j<k+1;j++)
		{
			if(j==4)
				System.out.print("     ");
			System.out.print(s[j] + "    ");
		}
		for(i=4;i<k+1;i++)
		{
			System.out.print("\n" + s[i]);
			for(j=4;j<k+1;j++)
			{
				System.out.print("    " + opm[i][j]);
			}
		}
	}
	public int[][] Multiplier(int[][] f,int[][] g,int[][] h )
	{
		int [][]arr1=new int[k+1][k+1];
		int [][]arr2=new int[k+1][k+1];
		int [][]arr3=new int[k+1][k+1];
		arr1[][];
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				for(w=1;w<k+1;w++)
				{

	}
	public int[][] Warshall(int[][] f)
	{
		int[][] arrplus = new int[k+1][k+1];
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				arrplus[i][j]=f[i][j];
			}
		}
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				if(arrplus[j][i]==1)
				{
					for(w=1;w<k+1;w++)
					{
						arrplus[j][w] = arrplus[j][w] | arrplus[i][w];
					}
				}
			}
		}
		Printer(arrplus,s);
		return(arrplus);
	}
	public int[][] Kleens(int[][] f)
	{
		int[][] arrstar = new int[k+1][k+1];
		for(i=1;i<k+1;i++)
		{
			for(j=1;j<k+1;j++)
			{
				arrstar[i][j]=f[i][j];
				if(i==j)
					arrstar[i][j]=1;
			}
		}
		Printer(arrstar,s);
		return(arrstar);
	}
	public void Printer(int[][] f,String[] s)
	{
		for(j=0;j<k+1;j++)
		{
			if(s[j]!=null)
				System.out.print(s[j] + "    ");
			else
				System.out.print("     ");
		}
		for(i=1;i<k+1;i++)
		{
			System.out.print("\n" + s[i]);
			for(j=1;j<k+1;j++)
			{
				System.out.print("    " + f[i][j]);
			}
		}
	}
	public void Printer(String[][] f,String[] s)
	{
		for(j=0;j<k+1;j++)
		{
			if(s[j]!=null)
				System.out.print(s[j] + "    ");
			else
				System.out.print("     ");
		}
		for(i=1;i<k+1;i++)
		{
			System.out.print("\n" + s[i]);
			for(j=1;j<k+1;j++)
			{
				System.out.print("    " + f[i][j]);
			}
		}
	}
}

class OPM
{
	public static void main(String[] args)
	{
		OPMatrix opmatrix = new OPMatrix();
		opmatrix.Matrix();
	}
}