1889 kotomi and function

PRoblem B: kotomi and function

Description

kotomi最近在研究函数，突然想到一个有趣的函数。 f(n) = n的各位数字之和。例:f(233) = 2 + 3 + 3 = 8 现在有n个数，stm要询问q次。 每次询问一个y，stm都要知道在a1,a2,...,ay-1中最大的数t使得f(t) = f(ay)

Input

输入有T组数据。(1 <= T <= 5) 第一行给出n,q。(1 <= n <= 100000 ,1 <= q <= 100000) 接下来n行给出n个数字a1,a2,...,an (1 <= ai <= 1000000000) 接下来q行每行给出一个数字y。(1 <= y <= n)

Output

对于每组数据，每行输出"Case #t:",t是编号，从1开始。 接下来q行，每行一个答案。如果不存在则输出-1。

Sample Input

1 
6 6
1 
2 
20 
11 
4 
1
6 
5 
4 
3 
2 
1


Sample Output

Case #1:
1
-1
20
2
-1
-1


HINT




每次输入第i数个a[i]的时候 判断该编号i之前有没有对应与f(a[i])相同的f(a[x]) (x<i) ,如果没有ans[i]就是-1，如果有ans[i]就是a[x];
并且按顺序每次遇到f(a[y])相同的数时，记录最大的a[y]。
#include <stdio.h>
#include <string.h>
int main()
{
    int t;
    scanf("%d",&t);
    for(int u=1;u<=t;u++)
    {
        int n,q,i,j,a[100100]={0},sumb[100100]={0},b[100100]={0},suma[100100]={0};
        int ans[100100]={0};
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
        {
            ans[i]=-1;
            scanf("%d",&a[i]);
            int k=a[i];
            while(k)
            {
                suma[i]=suma[i]+k%10;
                k=k/10;
            }
            if(sumb[suma[i]]>0)ans[i]=sumb[suma[i]]; // 如果suma[i]是第一次出现sumb[suma[i]]为0，则不存在，反之前面会有最大的a[x]存在
            if(a[i]>sumb[suma[i]])sumb[suma[i]]=a[i]; //记录最大，为后面做准备
        }
        printf("Case #%d:\n",u);
        for(i=1;i<=q;i++)
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
    }
    return 0;
}