Ladder

Interview

Time limit2sMemory limit64 MB

Summary

Given n sticks that can only be shortened, decide whether two can become length x and k others length y.

Level: Medium4 of 10
Topics: Greedy, Sorting, Array, Implementation
Solved: No attempts yet

Problem

You have $n$ sticks of lengths $d_1, d_2, \ldots, d_n$ . To build a ladder you need $k+2$ sticks: two sticks of length $x$ and $k$ sticks of length $y$ . You may shorten the sticks you have, but you cannot split one stick into two. Can you make a ladder?

Input

The first line contains a single integer $z$ , the number of test cases. The descriptions of the test cases follow.

Each test case consists of four integers $n$ , $k$ , $x$ , $y$ ( $1 \leq n \leq 10^5$ , $0 \leq k \leq 10^5$ , $1 \leq x, y \leq 10^9$ ) followed by $n$ integers $d_1$ , $d_2$ , $\ldots$ , $d_n$ ( $1 \leq d_i \leq 10^9$ ).

Output

For each test case, output a single line containing the word "YES" if making a ladder is possible, or "NO" otherwise.

Examples1

Example 1

Input

2
8 3 5 2
1 1 1 2 3 4 5 6
8 3 6 2
1 1 1 2 3 4 5 6

Expected output

YES
NO