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 *b*_{1}, …, *b*_{n},
and *m* white pieces with heights *w*_{1}, …, *w*_{m}.
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* = [*a*_{1}, *a*_{2}, *a*_{3}, *a*_{4}]
and *B* = [*b*_{1}, *b*_{2}, *b*_{3}, *b*_{4}]
(where *a*_{1} denotes the height of the bottom (black) piece of the pillar *A*,
*a*_{2} denotes the height of the second (white) piece of *A*, and so on),
we say that *A* is more stable than *B* if *a*_{1} > *b*_{1},
or if *a*_{1} = *b*_{1} but *a*_{2} > *b*_{2}, 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 · 10^{8}.
The second and third lines consist respectively
of *b*_{1}, …, *b*_{n} and of *w*_{1}, …, *w*_{m}.
A blank line separates two cases.
Assume 2 ≤ *n* ≤ 1000 and 2 ≤ *m* ≤ 1000,
and that no piece has a height larger than 10^{8}.

**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