Sum of Three Values

Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum is equal to the target, that is, nums[i] + nums[j] + nums[k] == target. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.

Note

A valid triplet consists of elements with distinct indexes. This means, for the triplet nums[i], nums[j], and nums[k], i ≠ j, i ≠ k, and j ≠ k.

Constraints

• 3 ≤ nums.length ≤ 500
• −10³ ≤ nums[i] ≤ 10³
• −10³ ≤ target ≤ 10³

Examples

Example 1

Input: nums = [3, 7, 1, 2, 8, 4, 5] target = 20

Output: True

Example 2

Input: nums = [-1, 2, 1, 4] target = 1

Output: False

Example 3

Input: target = 1

Output: True