PIHU1 - Love Story 1

Rancho is in love with Pihu. So on the Valentine’s Day they decided to spend time together at Assi Ghat, but Rancho, as we all know is very busy with his work, so he failed. It was now Pihu’s turn to go mad with anger. But there’s something which you can do.

Rancho tells Pihu that he is a novice programmer and is generally busy in solving problems at SPOJ. So Pihu decides to check his algorithmic skills. She puts forward an array of N integers. She gives him a number P and asks if he can find three (strictly three) integers Ai Aj Ak (i ≠ j ≠ k) in the array, whose sum is equal to number P, i.e.

Ai + Aj + Ak = P.

Now, sooner Rancho answers her query in YES or NO, sooner he gets a kiss.

Input

The first line of input consists of an integer T, the number of test cases.

The second line of input consists of an integer N denoting the size of array.

The third line consists of N integers A1, A2, A3 ... AN, separated by space.

The fourth line consists of number P.

Constraints

1 <= T <= 15

3 <= N <= 1000

1 <= Ai <= 10^9 where 1 <= i <= N

1 <= P <= 3*10^9

Output

If you find three numbers Ai, Aj, Ak, (i ≠ j ≠ k) in the array such that Ai + Aj + Ak =P, print “YES” else print “NO” (quotes for clarification only).

Example

Input:
1
3
1 2 3
6

Output
YES

After helping Rancho, would you like to help Pihu? Wink. Try PIHU2.


Added by:sobriquet
Date:2014-01-27
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:My own problem

hide comments
2020-06-26 12:38:32
use ll for P

Last edit: 2020-06-26 12:46:45
2019-04-13 07:56:13
By applying the concept of two pointer we can solve this problem in O(nlog(n)+n^2) .
2018-09-28 15:43:34
n^2 log(n) ... be careful , P is bigger than an Int datatype..
Easy question !
2018-07-25 13:40:19
O(N^3) works fine ! AC in one go.
2018-01-23 19:17:43
good problem think cool
2017-12-01 19:08:30
simple two pointer technique...
2017-11-22 10:09:10
unsigned long long + O(nlogn + n^2logn) = AC :D :D
2017-07-29 08:10:40
sort + TwoPointers Accepted....
2017-06-18 12:03:20
think simple....use long long .....int gives wa
2016-08-17 17:32:56 Shubham Gupta
Kindly check the input cases. Is there any value which is out of bound?
int sol: WA
unsigned long long: Passed!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.