You are given an array \(A\) of \(Q\) integers and \(Q\) queries. In each query, you are given an integer \(i\ (1≤i≤N)\).

Your task is to find the minimum index greater than \(i\ (1≤i≤N)\) such that:

1. Sum of digits of \(A_i\) is greater than the sum of digits of \(A_j\)
2. \(A_i\) < \(A_j\)

If there is no answer, then print -1.

Input format

• The first line contains two numbers \(N\) and \(Q\).
• The next line contains \(N\) numbers.
• Next \(Q\) lines contain \(Q\) queries.

Output format

Print the answer as described in the problem

Constraints

\({(1 \le N,\ Q\le 10^5)}\\ {(1 \le A_i \le  10^9)}\\ {(1 \le Q_i\le  N)}\)