//for cis3362
//By: Hua Zhang
//Date: October 21 2006

import java.io.*;
import java.math.*;

public class LFSR {

	public static void main(String[] args) throws Exception{
		int iSize; //size of the LFSR
		long lRegister; //contents of the register
		long lRule; //the rule
		int iStep; //number of steps
		String strOutFile; //name of the output file
		int iShiftBit; //bit that will be shifted in
		long lPow; // 2 to the order of the size of LFSR -1
		int i;
		long lTmp;
		String strOutput;
		BufferedWriter fWriter;
		BufferedReader stdin = new BufferedReader (new InputStreamReader(System.in));
		
		//read in user choice
		//1. size of LFSR
		System.out.println("What is the size of your LFSR?");
		iSize = Integer.parseInt(stdin.readLine());
		//2. initial contents of the register
		System.out.println("What are the contents of the original register?");
		lRegister = Long.parseLong(stdin.readLine());
		//3. rule
		System.out.println("What rule would you like to use?");
		lRule = Long.parseLong(stdin.readLine());
		//4. steps
		System.out.println("How many steps do you want to run the LFSR?");
		iStep = Integer.parseInt(stdin.readLine());
		//5. output file name
		System.out.println("What file would you like the output to be stored?");
		strOutFile = stdin.readLine();
		
		//open the output file
		fWriter = new BufferedWriter(new OutputStreamWriter 
				(new FileOutputStream(strOutFile)));
		//prepare 2 to the order of size of LFSR -1, used to set shift-in
		lPow = (long)Math.pow(2, iSize-1);
		for (i=0; i <= iStep; i++) {
			//calculate the bit that will be shifted in
			//1. clear all bits not selected by the rule
			lTmp = lRegister & lRule;
			//2. the xor of all bits will be the same as those bits selected,
			//as all other bits are 0
			if ((Long.bitCount(lTmp) % 2) == 0) {
				//even number of 1's, the XOR is 0
				iShiftBit = 0;
			} else {
				//odd number of 1's, the XOR is 1
				iShiftBit = 1;
			}
			
			//make the output string
			//the register
			strOutput = Long.toBinaryString(lRegister);
			//0's at the front might be ignored
			while (strOutput.length() < iSize) strOutput = "0" + strOutput;
			//the tab
			strOutput = "\t"+strOutput;
			//the shift-in bit
			strOutput = Integer.toString(iShiftBit) + strOutput;
			
			//write to output file
			fWriter.write(strOutput);
			fWriter.newLine();
			fWriter.flush();
			
			//shift the register with specified shift-in bits
			//1. shift the register, 0 will be shifted in
			lRegister = lRegister >> 1;
			//2. change the shift-in bits if necessary
			if (iShiftBit == 1) lRegister = lRegister | lPow;
		}
		fWriter.close();
	}

}