PMCA Sunday 10:00 Practice -03.21

Use Stack to solve the following question:

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:
Sum of digits of Ai is greater than the sum of digits of A_j
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≤N, Q≤105)(1≤A_i≤109)(1≤Q_i≤N)

Sample Input
5 5
62 70 28 62 92
1
5
3
4
2

Sample Output
2
-1
4
-1
-1

Explanation
In the first quary 70 grater than 62 
and sum of digits of 62 = 8 grater than sum f digits of 70=7 (8>7)