Given a collection of candidate numbers candidates (which may contain duplicates) and a target number target, find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input:
10 1 2 7 6 1 5
8
Output:
1 1 6
1 2 5
1 7
2 6

Example 2:

Input:
2 5 2 1 2
5
Output:
1 2 2
5

Constraints:

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30

Input format: First line: space-separated candidates. Second line: target.

Output format: Each combination on its own line, elements sorted ascending, combinations in lexicographic order.