Robot Project

Interview

Time limit5sMemory limit256 MB

Summary

Given a target length and up to a million rod lengths, find two rods summing exactly to the target with the maximum length difference, or report impossibility.

Level: Medium4 of 10
Topics: Two pointers, Sorting, Array
Solved: No attempts yet

Problem

Sang-geun and Sun-young are building a robot for a school assignment. While building it, they realize they need exactly two LEGO pieces to plug a hole in the robot.

The hole is $x$ centimeters wide, and the lengths of the two pieces placed into the hole must sum to exactly the width of the hole. If they do not match exactly, the robot breaks during the demonstration and the two of them receive an F. The hole must always be plugged with two pieces.

They have already measured the length of every LEGO piece in the physics lab precisely. Write a program that finds two pieces that plug the hole perfectly.

Input

The input consists of several test cases and is processed until end of file.

The first line of each test case contains the hole width $x$ ( $1 \le x \le 20$ , $x$ is an integer) in centimeters.

The second line contains the number of LEGO pieces $n$ ( $0 \le n \le 1000000$ ).

Each of the next $n$ lines contains the length $\ell$ of one LEGO piece. $\ell$ is a positive integer given in nanometers, and no piece is longer than $10$ centimeters ( $100000000$ nanometers).

(One centimeter equals $10000000$ nanometers.)

Output

Print one line for each test case. If there are no two pieces that plug the hole perfectly, print danger. Otherwise print yes ℓ1 ℓ2, where $\ell_1 \le \ell_2$ .

If several choices of two pieces are possible, print the one for which $|\ell_1 - \ell_2|$ is largest.

Examples7

Example 1
Input
```
1
4
9999998
1
2
9999999
```
Expected output
```
yes 1 9999999
```
Example 2
Input
```
1
3
5000000
3000000
1
```
Expected output
```
danger
```
Example 3
Input
```
5
0
```
Expected output
```
danger
```

Example 4

Input

Expected output

yes 5000000 15000000

Example 5

Input

Expected output

yes 10000000 10000000

Example 6
Input
```
2
2
10000000
3000000
```
Expected output
```
danger
```

Example 7

Input

Expected output

yes 1 9999999