Pillars P85783


Statement
 

pdf   zip

html

The world-famous architect Mr. Fruí from Reus is planning to build a colossal pillar H units high. Mr. Fruí has n black pieces with heights b1, …, bn, and m white pieces with heights w1, …, wm. According to his design, the pillar must have four pieces: a black piece at its bottom, a white piece above it, another black piece above, and finally a white piece at the top of the pillar.

Mr. Fruí wishes to know which combination of four pieces with total height H is the most stable. Given two combinations A = [a1, a2, a3, a4] and B = [b1, b2, b3, b4] (where a1 denotes the height of the bottom (black) piece of the pillar A, a2 denotes the height of the second (white) piece of A, and so on), we say that A is more stable than B if a1 > b1, or if a1 = b1 but a2 > b2, etc. In other words, A is more stable than B if and only if the sequence of heights of the pieces of A is lexicographically larger than the sequence of heights of the pieces of B.

Write a program such that, given the desired height H of the pillar, the heights of the black pieces and the heights of the white pieces, computes which pillar (if any) of height exactly H would be the most stable.

Input

Input consists of several cases, each in three lines. The first line has H, an integer number between 1 and 4 · 108. The second and third lines consist respectively of b1, …, bn and of w1, …, wm. A blank line separates two cases. Assume 2 ≤ n ≤ 1000 and 2 ≤ m ≤ 1000, and that no piece has a height larger than 108.

Output

For every case, print the sequence of heights of the pieces of the most stable pillar, from bottom to top. If no solution exists, print “no solution”.

Public test cases
  • Input

    100
    20 20
    30 10 30 50
    
    100
    20 10 4
    50 30 45
    

    Output

    20 50 20 10
    no solution
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Segon Concurs de Programació de la UPC - Final
    Date
    2004-09-29