Find the k Closest Elements

You are given a sorted array of n integers and two additional integers k and x. Your task is to find the k closest integers to x from the array.

The answer must be returned in sorted ascending order.

More formally, given an array \(A = [a_1, a_2, \ldots, a_n]\) (where \(a_1 \leq a_2 \leq \cdots \leq a_n\)), an integer \(k\) and a target integer \(x\), you need to find the subarray \(B = [b_1, b_2, \ldots, b_k]\) such that:

• For every \(b_i \in B\), \(|b_i - x|\) is as small as possible among the elements in \(A\).
• If there is a tie, the smaller element is preferred.

Hint: You can achieve an efficient solution using a binary search based approach. The range of possible starting indices for the answer is from \(0\) to \(n-k\). By using binary search on this range, you can determine the optimal index where the subarray of length \(k\) begins.

The relevant decision step in binary search is based on the comparison:

\[ x - A[\text{mid}] \quad vs. \quad A[\text{mid}+k] - x \]

If \(x - A[\text{mid}] > A[\text{mid}+k] - x\), then \(A[\text{mid}]\) is less favorable, so you should move to the right half of the search space.

inputFormat

The first line of input contains three integers: n (the number of elements in the array), k (the number of closest elements to find), and x (the target integer).

The second line contains n space-separated integers representing the sorted array.

For example:

5 4 3
1 2 3 4 5

outputFormat

Output the k closest integers to x in ascending order, separated by a single space.

For example, for the sample input above, the output should be:

1 2 3 4

## sample

5 4 3
1 2 3 4 5

1 2 3 4