Find the minimum number sum of digits of special number that sums to a number N

A special number is a number of the form {..., 111, 11 , 1 , -1, -11, 111, .....}

$$$1 <= N <= 10^{12}$$$

Example

Input 19

output 7

Explanation 11 + 11 + (-1) + (-1) + (-1)

2 + 2 + 1 + 1 + 1 = 7 digits

You are given an array A of N integers.

Create another array B containing all or-subarrays of A . i.e B contains $$$A_{l}|A_{l+1}|...A_{r}$$$ for all $$$1 <= l <= r <= N$$$

You are provided Q queries . n each query you have to print K-th smallest element of B.

$$$1 <= A_{i} <= 10^{5}$$$ $$$1 <= Q , N <= 10^{5}$$$ $$$1 <= k <= N*(N+1)/2$$$

Example

N = 3 A = [1, 2, 3] Q = 3 Queries = [1, 2, 6]

B = {1, (1|2), (1|2|3), 2, (2|3), 3} = {1, 3, 3, 2, 3, 3}

The queries are answered below

• The 1st smallest element is 1

• The 2nd smallest element is 2

• The 6th smallest element is 3.