Railroad#1807
A train yard is a complex system of railroad tracks used for storing, sorting, or loading/unloading railroad cars. In this problem, the railroad tracks are much simpler, and we are only interested in combining two trains into one.
Each of the two trains consists of several railroad cars. Each railroad car contains a single type of product, identified by a positive integer up to . The two trains arrive from the right on separate tracks, as shown in the diagram above. To combine the two trains, you may take the railroad car at the front of either train and attach it to the back of the new train being formed on the left. If all railroad cars from one train have already been moved, then the remaining cars from the other train will be moved to the left one at a time. All railroad cars must eventually be moved to the left. Depending on which train is chosen at each step, different arrangements can be formed for the departing train on the left. For example, the order 1,1,1,2,2,2 can be obtained by always choosing all cars from the top train first, or 2,1,2,1,2,1 by alternating cars from the two trains.
To facilitate further processing at other train yards later on (and at the destination), the supervisor at the train yard is given the desired order of products for the departing train. In this problem, you must decide whether it is possible to achieve the desired ordering, given the order of products for the two trains arriving at the train yard.
The input consists of multiple cases. The first line contains two positive integers N_1 N_2, indicating the number of railroad cars in each train (at least and at most cars per train). The second line contains N_1 positive integers (up to ) giving the products on the first train from front to back. The third line contains N_2 positive integers identifying the products on the second train (in the same format). The fourth line contains N_1 + N_2 positive integers representing the desired order for the departing train (same format).
The end of input is indicated by N_1 = N_2 = 0.
For each case, print on a line possible if it is possible to produce the desired order, or not possible otherwise.
Example 1