Four Sum

Given an array of integers and a target integer, find all unique quadruplets \(a, b, c, d\) such that:

\(a + b + c + d = target\)

The quadruplets should not contain duplicate solutions and each quadruplet must be sorted in non-decreasing order. The overall output should be listed in lexicographical order.

Example:

Input: 6
       1 0 -1 0 -2 2
       0
Output:
-2 -1 1 2
-2  0 0 2
-1  0 0 1

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the elements of the array.
3. The third line contains an integer representing the target value.

outputFormat

Print each unique quadruplet that sums to the target on a separate line. Within each line, print the four numbers separated by a single space. The quadruplets must be sorted in lexicographical order. If no such quadruplet exists, output an empty line.

## sample

6
1 0 -1 0 -2 2
0

-2 -1 1 2
-2 0 0 2
-1 0 0 1

</p>