/**
 * Code for exercise 3
 * Lecture Series Informatik II D-BAUG ETH Zürich  
 * Felix Friedrich, Georg Ofenbeck, Lars Widmer
 */

class LCG { //this is the random number generator from last exercise
	static final long m = 2147483647;
	static final long b = 12345;
	static final long a = 1103515245;
	static long u = 0; //to use within the judge we fix the "seed", such that we always get the same random numbers
	
	public static double Uniform(){
		u = (u * a + b) % m;
		return(double)u/m;
	}
}

// provide your modifications in this class only
class RandomSurfer{		
	
	// pre: non-empty matrix m
	// post: matrix printout on System.out
	public static void printMatrix(double[][] m) {
		int rows = m.length;
		int cols = m[0].length;
		System.out.println(rows + " " + cols);
		for(int r = 0; r < rows; r++){									
			for (int c = 0; c < cols; c++){
				System.out.printf("%7.5f ", m[r][c]);
			}
			System.out.println("");
		}
	}

	// pre: matrix data provided via scanner
	// post: returns matrix data
	public static double[][] readMatrix(java.util.Scanner scanner){		
		int M = scanner.nextInt(); // Zeilen
		int N = scanner.nextInt(); // Spalten
		// Daten
		double[][] p = new double[M][N];     
	  	for (int i = 0; i < M; i++)
	  		for (int j = 0; j < N; j++) 
				p[i][j] = scanner.nextDouble(); 
		return p;
	}
	
	// pre: non-empty input vector of length N, matrix of size N times M
	// post: return vector-matrix product v * m. Vector of size M
	public static double[] multiplyVectorMatrix(double[] v, double[][] m) {
		int N = v.length;
		int M = m[0].length;
	    double[] res = new double[M]; // result vector
	    for (int c=0; c < M; ++c) { // for every column of the matrix
	    	res[c] = 0; // initial value (actually also done by the java VM)
	        for (int r=0; r<N; ++r) // for every element of the vector
	        	res[c] += m[r][c] * v[r]; // += adds the product to res[j] 
	    }
	    return res;
	}

	// single step simulation from the lecture
	public static int simulateLine(double[] prob)
	{
		int res=0;
		double r = LCG.Uniform(); 
		double sum = 0.0; 
		for (int j = 0; j < prob.length; j++) {
			sum += prob[j]; 
			if (r < sum) {res = j; break;}
		}
		return res;
	}
	
	// pre: non-empty probability matrix P, t >= 0 number of steps
	// post: return relative frequencies of visits in each point
	//	       after MCMC simulation until convergence reached
	public static double[] simulate(int t, double[][] P) {					
		int N = P.length;
		int[] freq = new int[N];  // freq[i] = # times surfer hits page i
		int page = 0; 				// start at page 0
		double[] inv_freq = new double [N];
		
		for (int j = 0; j < t; j++) {
			page = simulateLine(P[page]);
			freq[page]++;
			long sum = 0;
			for(int i = 0; i < freq.length; i++) sum += freq[i];			
			for(int i = 0; i < freq.length; i++) inv_freq[i] = (double)1.0/sum*freq[i];
		}
		
		return inv_freq;
	}
	
	// pre: non-empty probability matrix P, i >= 0 number of iterations
	// post: return vector-matrix product v * m after i iterations
	public static double[] multipleMultiplications(int i, double[] v, double[][] m) {
		for (int j = 0; j < i; j++) {
			v = multiplyVectorMatrix(v, m);
		}
		return v;
	}
	
	// pre: non-null vector
	// post: vector output to standard out
	public static void show(double[] v) {
		for (int i=0; i<v.length; ++i)
			System.out.printf("%7.5f ",v[i]);
		System.out.println();
	}

}


//---------------------------------------------------------------------------------
// Unfortunately it is a restriction of the judge that we always have to have a public class Main in our file
// The code below is only used to validate your code with the judge - feel free to browse - but its not required for the exercise
//------------------------------------------------------------------------------------------------------------------------
class Main{ 
	
	public static double[] readV(java.util.Scanner scanner){		
		int n = scanner.nextInt();
		double[] res = new double[n];     
	  	for (int i = 0; i < n; i++)
	  		res[i] = scanner.nextDouble(); 
		return res;
	}
		
	public static void main(String[] args) {
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		int choice = scanner.nextInt();
		
		if (choice == 1){
			double[][] matrix = RandomSurfer.readMatrix(scanner);
			RandomSurfer.printMatrix(matrix);
		}
		if (choice == 2) {
			double[] vector = readV(scanner);
			double[][] matrix = RandomSurfer.readMatrix(scanner); 
			RandomSurfer.show(RandomSurfer.multiplyVectorMatrix(vector,matrix));
		}
		if (choice == 3) {
			int steps = scanner.nextInt();
			double[][] matrix = RandomSurfer.readMatrix(scanner); 
			RandomSurfer.show(RandomSurfer.simulate(steps, matrix));
		}
		if (choice == 4) {
			int iterations = scanner.nextInt();
			double[] vector = readV(scanner);
			double[][] matrix = RandomSurfer.readMatrix(scanner);
			RandomSurfer.show(RandomSurfer.multipleMultiplications(iterations, vector, matrix));
		}
	}
}

/*
data that can be used to check (use copy and paste to check)

3.1.1 ReadMatrix Input (choice 1):
1
2 3
1 2 3 4 5 6

Expected output:
2 3
1.00000 2.00000 3.00000 
4.00000 5.00000 6.00000

3.1.2 MutiplyVectorMatrix Input (choice 2):
2
3
1 2 3
3 3 
1 2 3
4 5 6
7 8 9

Expected output:
30.00000 36.00000 42.00000 

3.1.3 Simulate Input (choice 3):
3
10000000
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000 

Expected output:
0.32517 0.22769 0.12524 0.14370 0.17821

3.1.4 Optional Input (choice 4):
4
100
5
1.0 0.0 0.0 0.0 0.0
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000

Expected output:
0.32520 0.22741 0.12540 0.14366 0.17832 
*/