That's One Hanoi-ed Teacher

Time limit2sMemory limit512 MB

Summary
Given a legal Tower of Hanoi layout, decide whether it lies on the optimal solution path and if so output the remaining moves to the goal.
Level

Medium7 of 10

Topics
Recursion, Divide and conquer, Implementation
Solved
No attempts yet

Problem

Roberta teaches math at a small college, and she has just introduced the Tower of Hanoi to her discrete math class. The puzzle has three pegs and nn disks with radii 1,2,…,n1, 2, \ldots, n. At the start every disk sits on the start peg, ordered by increasing size from top to bottom. The object is to move all of them to the destination peg under two rules:

  1. You move only one disk at a time.
  2. At no point may a larger disk lie on top of a smaller disk.

The optimal solution for nn disks takes 2n−12^n - 1 moves, so it passes through exactly 2n2^n configurations, counting the start and the goal. The picture below shows the optimal solution for n=3n = 3, with the start peg on the left and the destination peg on the right.

While the students work, Roberta wants to look at a layout and decide whether it is one of those 2n2^n configurations. If it is, she also wants to tell the student how many moves are left to the goal, which is every disk stacked on the destination peg in decreasing size from bottom to top. Write the program she asks for.

Input

Input consists of three lines, each line representing one peg. Each line starts with a non-negative integer mm, the number of disks on that peg, followed by mm integers listing those disks from the bottom of the peg upward. The first line is the start peg and the third line is the destination peg. Disk numbers are the consecutive integers 11 to nn, where the number is the radius of the disk, and 1≤n≤501 \le n \le 50. The given layout is a legal configuration of the puzzle: on every peg the radii strictly decrease from bottom to top.

Output

Print No if the given configuration is not in the optimal solution sequence. Otherwise print the minimum number of moves still required to reach the goal configuration.

Examples6

  1. Example 1

    Input
    1 3
    2 2 1
    0
    
    Expected output
    4
    
  2. Example 2

    Input
    1 3
    0
    2 2 1
    
    Expected output
    No
    
  3. Example 3

    Input
    0
    0
    1 1
    
    Expected output
    0
    
  4. Example 4

    Input
    1 1
    0
    0
    
    Expected output
    1
    
  5. Example 5

    Input
    0
    1 1
    0
    
    Expected output
    No
    
  6. Example 6

    Input
    3 3 2 1
    0
    0
    
    Expected output
    7