猫史档案馆

题目背景

小T在研究直升机方面已经积累了不少成果，从一开始制造的“昂贵的直升机”，到后来能造出“便宜的直升机”，随后很快就实现了“量产直升机”。现在的小T更是研发出了各类不同型号的直升机，开设了一家直升机专卖店。

题目描述

直升机专卖店里生意火爆，正对外招聘导购员。导购员的职责是向每一位顾客推荐最合适的产品，提高顾客的购买率。

具体的，专卖店里有 � 款不同型号的直升机，按 1∼� 编号。每款直升机都有对应的售价，编号 � 型号的直升机售价为 ��。

每名到店的顾客，都会告知导购员他的预算金额 ��，只要给顾客推荐了合适的型号，顾客就一定会将预算金额尽可能多的用于购买直升机。导购员需按如下规则向顾客推荐合适的型号：

• 优先推荐恰好能花完预算金额的型号
• 如有多款型号能花完预算金额，优先推荐可购买数量最多的型号
• 如上述两条规则可推荐的型号不止一种，优先推荐编号最大的型号
• 如没有满足上述条件的型号，优先在顾客买得起的型号中，推荐当前售出数量最多且编号尽可能小的型号
• 如果没有顾客买得起的型号，则推荐的编号记为 -1

现在专卖店开业了，先后来了 � 位顾客，你身为新入职的导购员，对于每位顾客要准确的推荐合适的型号 ��，同时记录该顾客消费后实时的营业额（收入总金额）��。

输入格式

第一行两个整数 �,�，表示直升机型号种类数和到店的顾客数。

第二行 � 个整数，对应编号 1∼� 型号的售价 ��。

接下来 � 行，每行一个整数 ��，对应从开业起依次到店的顾客的预算金额。

输出格式

共 � 行，每行输出两个整数 ��,��，空格隔开，表示推荐给对应顾客的直升机型号编号和该顾客消费后的实时营业额。

样例数据 输入样例 #1

7 5
4 6 7 8 14 19 22
38
56
32
23
3

输出样例 #1

6 38
1 94
1 126
1 146
-1 146

数据范围 子任务 特殊性质 1(10pts) �=1 2(10pts) �=1 3(10pts) 1≤��≤102,1≤��≤104 4-5(20pts) 保证每个顾客都能恰好花完预算金额 6-7(20pts) �≤103 8-10(30pts) 无

对于 100% 的数据，1≤�≤105,1≤�≤100,1≤��≤107,1≤��≤109。