import java.math.BigInteger;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String A = scanner.nextLine();
		String[] aTab = A.split(" ");
		String N = scanner.nextLine();
		String[] nTab = N.split(" ");
		int nLegnth;
		int nPodstawa = 0;
		int mLength = 0;
		int cLength = 0;
		int a = 0;
		int nTabLength;
		int[] nTabNumber = null;
		try{
		int nLength = Integer.parseInt(aTab[0]);
		if(nLength < 1 || nLength > Math.pow(10, 7)){
			System.exit(0);
		}
		nPodstawa = Integer.parseInt(aTab[1]);
		if(nPodstawa < 3 || nPodstawa > Math.pow(10, 9)){
			System.exit(0);
		}
		mLength = Integer.parseInt(aTab[2]);
		if(mLength < 2 || mLength > Math.pow(10, 3)){
			System.exit(0);
		}
		cLength = Integer.parseInt(aTab[3]);
		if(cLength < 2 || cLength > Math.pow(10, 3)){
			System.exit(0);
		}
		nTabLength = nTab.length;
		nTabNumber = new int[nTabLength];
		a = nTabLength - 1;
		}catch(NumberFormatException ex){
			System.exit(0);
		}
		while (a >= 0) {
			nTabNumber[a] = Integer.parseInt(nTab[a]);
			a = a - 1;
		}
		int nTabNumberLength = nTabNumber.length;
		while(nTabNumberLength > 0 ){
			if(nTabNumber[nTabNumberLength-1] < 0 || nTabNumber[nTabNumberLength-1] > nPodstawa-1){
				System.exit(0);
			}
			nTabNumberLength--;
		}
		for(int z : nTabNumber){
			if(z < 0 || z > (nPodstawa)){
				System.exit(0);
			}
		}
		BigInteger big = new BigInteger("0");
		int c = 0;

		BigInteger BiNPodstawa = new BigInteger(aTab[1]);
		while (c < nTab.length) {
			BigInteger BiNtabNum = new BigInteger(nTab[nTab.length - c - 1]);
			BigInteger BiPowSum = BiNPodstawa.pow(c);
			BigInteger BiMultiplySum = BiNtabNum.multiply(BiPowSum);
			big = big.add(BiMultiplySum);
			c++;
		}
		String bigToString = big.toString();
		BigInteger bi = new BigInteger(bigToString);
		String binarySum = bi.toString(2);

		int binarySumLength = binarySum.length();
		String[] binTab = binarySum.split("");
		for (int i = 0; i < binTab.length; i++) {
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < nTab.length; i++) {
			sb.append(nTab[i]);
		}
		String afterSb = sb.toString();
		BigInteger aNum = new BigInteger(afterSb);
		int znak = 0;
		String compareStr = "0";
		BigInteger compareBi = new BigInteger(compareStr);
		znak = 0;
		if (aNum.compareTo(compareBi) == -1) {
			znak = 1;
		}

		StringBuilder sbMantysa = new StringBuilder();
		sbMantysa.append(znak);
		long dlugoscMantysy = mLength - 1;
		if(mLength <= binTab.length){
			for(int i = 0; i <dlugoscMantysy; i++){
				sbMantysa.append(binTab[i]);
			}
		}else if(mLength > binTab.length){
				for(int i =0; i<binTab.length; i++){
					sbMantysa.append(binTab[i]);
				}
				int d = sbMantysa.length();
				while(d < mLength){
					sbMantysa.append(0);
					d++;
				}
			}
		String mantysaStr = sbMantysa.toString();
		BigInteger closeNBi = new BigInteger(mantysaStr, 2);
		closeNBi = closeNBi.shiftLeft(1);
		String closeN = closeNBi.toString(2);
		int closeNLength = closeN.length();
		StringBuilder closeNbuilder = new StringBuilder();
		closeNbuilder.append(closeN);
		if(closeNLength < binarySumLength){
			int y = closeNLength;
			while(y != binarySumLength){
				closeNbuilder.append(0);
				y++;
			}
		}
		String closeNfinale = closeNbuilder.toString();
		BigInteger BiCloseFinale = new BigInteger(closeNfinale, 2);
		BigInteger mantysaFinale = new BigInteger(mantysaStr, 2);
		BigInteger dividingResult = BiCloseFinale.divide(mantysaFinale);
		String dwa = "2";
		String jeden = "1";
		BigInteger two = new BigInteger(dwa);
		BigInteger one = new BigInteger(jeden);
		int divingResult1 = 0;
		int cecha = 0;
		int compare = 1;

		BigInteger temp = dividingResult;
		while(compare != 0){
			BigInteger res = temp.divide(two);
			temp = res;
			compare = temp.compareTo(one);
			cecha++;
		}
		String cechaStr = Integer.toString(cecha);
		BigInteger biCecha = new BigInteger(cechaStr);
		String cechaFinale = biCecha.toString(2);
		int cechaFinaleLength = cechaFinale.length();
		StringBuilder cechaBuilder = new StringBuilder();
		if(cechaFinaleLength < cLength){
		int z = cechaFinaleLength;
		while(z != cLength){
			cechaBuilder.append(0);
			z++;
		}
		cechaBuilder.append(cechaFinale);
		}else if(cechaFinaleLength > cLength){
			String[] cechaTab = cechaFinale.split("");
			int z = 0;
			while(z < cLength){
				cechaBuilder.append(cechaTab[z]);
				z++;
			}
		}
		String cechaFinaleStr = cechaBuilder.toString();
		String[] cechaTab = cechaFinaleStr.split("");
		StringBuilder cechaFinaleBuilder = new StringBuilder();
		if(mLength > binTab.length){
			int h =0;
			while(h < cechaTab.length){
				if(cechaTab[h].equals("0")){
					cechaTab[h] = "1";
				}else if(cechaTab[h].equals("1")){
					cechaTab[h]="0";
				}
				h++;
			}
			for(int i=0; i<cechaTab.length; i++){
				cechaFinaleBuilder.append(cechaTab[i]);
			}
			cechaFinaleStr = cechaFinaleBuilder.toString();
		}
		System.out.println(mantysaStr);
		System.out.println(cechaFinaleStr);
	}
}