Tower of Hanoi

In the Tower of Hanoi, n disks stacked on one of three rods are moved to another rod. You may move only one disk at a time, and a larger disk may never be placed on a smaller disk. The minimum number of moves needed to move a full stack is 2^n - 1.

Donghyuk made a mistake while moving the disks, so the disks are now split among the three rods. The rules were never violated, so on each rod the disk numbers get smaller from bottom to top.

From the current state, gather all disks onto a single rod using the fewest moves. Determine which rod should receive all disks and the minimum number of moves. Because the count can be very large, output it modulo 1,000,000.

The first line contains an integer n (1 <= n <= 100,000), the number of disks.

The second line contains three integers a, b, and c, the numbers of disks on rods 1, 2, and 3. Each value is between 0 and n, and a + b + c = n.

The next three lines describe rods 1, 2, and 3 in order. Each line lists the disk numbers on that rod from bottom to top. Disk numbers are 1 through n, and the input is always a valid state.

Print the number of the rod where all disks should be gathered on the first line.

On the second line, print the minimum number of moves modulo 1,000,000.