Fixing an Array

Time limit2sMemory limit128 MB

Summary

For each array value, find the number within a given range that has the smallest Hamming distance in binary, breaking ties by choosing the smallest value.

Level: Medium7 of 10
Topics: Bit manipulation, Dynamic programming, Greedy
Solved: No attempts yet

Problem

You are given an integer array A and two integers low and high. Construct an array B with the same length as A.

Every element X of B must satisfy low <= X <= high. For each index i, choose B[i] so that the bit difference between A[i] and B[i] is minimized. If multiple arrays B satisfy these minimum distances, output the lexicographically smallest one.

The bit difference between two integers a and b is computed as follows. Write both numbers in binary. If their lengths differ, pad the shorter binary representation on the left with 0s until the lengths match. Then count the positions where the two bits are different.

Input

The first line contains the size N of array A and two integers low and high.

The second line contains the elements A_i of array A, separated by spaces.

Output

Print the elements of array B on one line, separated by spaces.

Constraints

1 <= N <= 50
0 <= low <= high <= 2^30 - 1
0 <= A_i <= 2^30 - 1

Examples5

Example 1
Input
```
1 101 105
71
```
Expected output
```
103
```

Example 2

Input

5 98 304
12 65 302 1 1000000

Expected output

140 193 302 129 192

Example 3
Input
```
1 16 16
1000000
```
Expected output
```
16
```
Example 4
Input
```
1 83 92
48
```
Expected output
```
84
```
Example 5
Input
```
3 1 4
5 6 7
```
Expected output
```
1 2 3
```