#P9622. 拍照

拍照

题目描述

有 nn 支代表队参加了今年的 WF,代表队的编号分别为 1…n1\ldots n。每支队伍包含 mm 名选手。每支代表队的 T 恤的颜色都不一样,ii 号队伍的队色是第 ii 种颜色。

台上有 mm 处空位,空位的编号分别为 1…m1\ldots m。摄影师希望 ii 号空位最终站着穿第 aia_i 种颜色 T 恤的选手。

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

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

输入格式

第一行为两个正整数 m,nm,n。

第二行给出 mm 个整数 a1,ldots,ama_1,ldots,a_m,其中 1leailen1le a_ile n,表示每个空位的目标颜色。

输出格式

第一行为一个正整数 kk,表示你操作的步数。

接下来 kk 行,每行三个正整数 ci,Li,Ric_i,L_i,R_i,cic_i 表示摄影师选择队伍的编号。

无解请输出 −1-1。

样例

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

子任务

子任务 分数 m≤m\le n≤n\le
11 1515 100100
22 10410^4
33 55 3×1053\times 10^5 22
44 33
55 2020 1010
66 4040 3×1053\times 10^5