You have an array a composed of exactly n elements. Given a number x, determine whether or not a contains three elements for which the sum is exactly x.

Input/Output

[time limit] 3000ms

[input] integer x

Guaranteed constraints:
1 ≤ x ≤ 105.

[input] array.integer a

Guaranteed constraints:
3 ≤ a.length ≤ 6 · 105,

1 ≤ a[i] ≤ 105.

[output] boolean

Return true if the array contains three elements that add up to x and false otherwise.