#3187. 「ROI 2019 Day1」拍照

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2019 Day1 T1. Постановочное фото

n 支代表队参加了今年的 ROI,代表队的编号分别为 1\ldots n 。每支队伍包含 m 名选手。每支代表队的 T 恤的颜色都不一样, i 号队伍的队色是第 i 种颜色。

台上有 m 处空位,空位的编号分别为 1\ldots m 。摄影师希望 i 号空位上站的选手穿着第 a_i 种颜色的 T 恤。

摄影师每次可以要求一支队伍任选 R-L+1 名选手(不能超过该队的选手总数),站在 L\ldots R 号空位上,如果之前这些空位上站了选手,他们得从舞台上下来,把位置让给新上台的选手。摄影师不能重复叫同一支队伍。

请构造一组方案使得最终队列满足摄影师的要求。

输入格式

m\ n
a_1\ a_2\ \cdots\ a_m

输出格式

k
接下来 k 行,每行: c_i,L_i,R_i c_i 表示摄影师选择的队伍的编号。
无解请输出 -1

样例

样例输入 1

7 10
10 5 5 10 4 2 4

样例输出 1

5
4 1 7
7 2 4
10 1 4
5 2 3
2 6 6

样例输入 2

5 2
1 2 1 2 1

样例输出 2

-1

数据范围与提示

子任务 # 分值 m \le n \le
1 15 100
2 15 10^4
3 5 3\cdot 10^5 2
4 5 3
5 20 10
6 40 3\cdot 10^5