当前没有测试数据。

题目描述

在一个名为“Techtopia”的未来城市中，科技和创新是日常生活的核心。这座城市拥有一个多功能的社区中心，它不仅是居民们社交和娱乐的场所，也是举办各种活动和会议的中心。

社区中心有多个会议室和活动室，它们可以根据需要灵活配置，以适应不同的活动类型。由于社区中心非常受欢迎，居民们需要提前预订这些房间。

Techtopia的城市规划者们设计了一个智能预订系统，以确保会议室的公平和高效分配。系统需要处理来自不同居民和团体的预订请求，并按照先到先得的原则分配房间。

然而，由于房间数量有限，有时无法满足所有的预订请求。在这种情况下，系统需要及时通知申请者，并建议他们调整预订计划。

作为Techtopia社区中心的智能预订系统开发者，你需要编写一个算法来处理会议室的预订请求。给定一段时间内的会议室可用信息和一系列预订请求，你需要判断哪些请求可以被完全满足，哪些需要申请者进行调整。

输入格式

• 第1行：两个正整数n和m，分别表示考虑的天数和预订请求的数量。
• 第2行：n个正整数，表示每天社区中心可用于预订的会议室数量。
• 接下来m行：每行三个正整数d, s, t，分别表示每个预订请求所需的会议室数量、预订开始和结束的日期。

输出格式

• 如果所有预订请求均可满足，则输出只有一行，包含一个整数0。
• 如果有预订请求无法满足，输出两行，第一行输出一个负整数-1，第二行输出需要调整计划的申请者编号。

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

-1 
2

提示

对于10%的数据，有1≤𝑛,𝑚≤10；

对于30%的数据，有1≤𝑛,𝑚≤1000；

对于 70%的数据，有1≤𝑛,𝑚≤10^5；

对于 100%的数据，有1≤𝑛,𝑚≤10^6,0≤𝑟𝑖,𝑑𝑗≤10^9,1≤𝑠𝑗≤𝑡𝑗≤𝑛。