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)}$