import java.io.*;
import java.util.StringTokenizer;
import java.math.*;

public class CEOI2003hanoi2 {
  public int[] pileofDisc;
  public static int numMoves = 0;
  public CEOI2003hanoi2() {
  }

  public void moveDisc(int maxofDisc,
                       int dstPile) {
    if (maxofDisc < 1) {
      return;
    }
    int srcPile = pileofDisc[maxofDisc];
    int auxPile = 1 + 2 + 3 - srcPile - dstPile;
    if (srcPile != dstPile) {

      moveDisc(maxofDisc - 1, auxPile);

      int pow = 1;
      for (int i = 1; i < maxofDisc; i++) {
        pow = 2 * pow % 1000000;
      }

      numMoves = (int) (numMoves + pow) % 1000000;
      for (int i = 1; i <= maxofDisc; i++) {
        pileofDisc[i] = dstPile;
      }
    }
    else {
        moveDisc(maxofDisc - 1, dstPile);
      }
    }

    public void Start(int numberofDisc, int maxDisc
                      ) throws
        Exception {
      moveDisc(numberofDisc-1, maxDisc);
      System.out.println(pileofDisc[numberofDisc]);
      System.out.println(numMoves);
    }

    public static void main(String[] args) throws Exception {

      CEOI2003hanoi2 c2 = new CEOI2003hanoi2();
      BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
      String teststring = r.readLine();
      Integer y = new Integer(teststring);
      int numberofDisc = y.intValue();
      c2.pileofDisc = new int[numberofDisc + 1];
      teststring = r.readLine();
      for (int i = 0; i < 3; i++) {
        teststring = r.readLine();
        StringTokenizer st = new StringTokenizer(teststring);
        String s1 = "";
        while (st.hasMoreTokens()) {
          s1 = st.nextToken();
          y = new Integer(s1);
          int temp = y.intValue();
          c2.pileofDisc[temp] = i + 1;
        }
      }

      c2.Start(numberofDisc, c2.pileofDisc[numberofDisc]);
    }

  }