#P17859. [XV Open Cup]Analyze This

[XV Open Cup]Analyze This

题目描述

一家餐厅有 nn 位顾客,第 ii 位顾客每天在时刻 tit_i 到达。每天的餐点制作时间相同,但不同天可能不同。

某天制作一份餐点需要 DD 分钟。每位顾客到达后立即点餐,在时刻 ti+Dt_i+D 取餐并离开。餐厅可以同时处理任意多个订单。

顾客到达时,会与店主以及所有尚未离开的顾客握手。若一位顾客恰好在此时离开,两人仍会握手。已经在店内的顾客与新顾客握手时,他的愤怒值等于自己已经等待的分钟数。店主的愤怒值始终是 00。

给定 mm 天的制作时间 DjD_j,请分别找出一次能产生当天最大愤怒值的握手,输出参与握手的两个人的编号。顾客按输入顺序编号为 11 到 nn,店主编号为 00。

等价地,若选出两个不同顾客 a,ba,b,必须满足 ∣ta−tb∣≤Dj|t_a-t_b|\le D_j,产生的愤怒值为 ∣ta−tb∣|t_a-t_b|;店主与任意顾客握手产生的愤怒值为 00。你需要使这个值最大。

输入格式

第一行包含两个整数 n,mn,m。

第二行包含 nn 个整数 t1,t2,…,tnt_1,t_2,\ldots,t_n。到达时间不保证有序,也可能相同。

接下来 mm 行,每行包含一个整数 DjD_j。

输出格式

输出 mm 行。第 jj 行输出两个不同的人的编号 a,ba,b,表示第 jj 天选出的握手。两人的顺序任意;若有多个最优答案,输出任意一个。

数据范围

  • 1≤n,m≤4000001\le n,m\le400000;
  • 0≤ti<4000000\le t_i<400000;
  • 0≤Dj<4000000\le D_j<400000。

样例

3 4
1 2 5
0
5
1
3
0 1
1 3
1 2
2 3

样例解释

四天能产生的最大愤怒值依次为 0,4,1,30,4,1,3。