题目内容

小塔店主发现商品的出纳账单遭到了毁坏，为了恢复，他翻阅了近期的监控和商品出售记录，得到了每一个人到店的日期和在哪一个位置取过物品(但是由于监控模糊，只能大致确定区间)。

每一个商品都有剩余保质期，每过一天剩余保质期都应该减一，当保质期为非负数时，都会被人购买;当保质期为负数时，就没有人再会买了;

保质期先于人员到店刷新。

假设第$i$个客人在$day_i$天来商店购物，且在$[l,r]$这个货架区间取过物品，那么他会挑选靠左的保质期最长的那个商品走。

请你帮助计算每一个人买走的商品编号。

输入描述

第一行输入两个整数$n$和$m(1≤n,m≤10^5)$代表来小塔商店购物的人数和商品数量。

第二行输入$m$个整数$a_1,a_2,...,a_m(1≤a_i≤10^9)$代表商品的保质期。

此后$n$行，第$i$行输入三个整数$day_i,l_i和r_i(1≤day_i≤10^5;1≤l_i≤r_i≤m)$代表第$i$个人的到店时间、

取货区间。

如果有多个人在同一天到店，那么先输入的人早于后输入的人到店。

输出描述

输出一行，包含$n$个整数，代表每一个人买走的商品编号，如果这个人的取货区间里没有满足条件的商品，输出$-1$替代。

示例1

输入

4 5
1 2 3 4 7
1 1 4
1 4 4
5 1 4
5 1 5

输出

4 -1 -1 5

说明

• 对于第一个顾客，买走保质期最长的第四个商品；
• 对于第二个顾客，由于第四个商品已经被买走了，所有他没有买到商品，输出-1；
• 对于第三个顾客，由于他是第五天来的，此时前四个商品都已经过期了，所有他也没没有买到商品，则输出-1

样例2

输入

3 5
2 2 2 2 2
1 1 5
2 1 5
3 1 5

输出

1 2 -1