在全俄信息学奥林匹克竞赛集体合影前，首席摄影师决定为他在 Innogram 社交网络上的粉丝拍摄一张摆拍照片。

竞赛共有来自 $n$ 个地区的学生参加，每个代表团由 $m$ 名学生组成。每个地区的代表团都希望彰显个性，因此他们穿上了自己颜色的制服，该颜色与任何其他地区的制服颜色都不相同。我们将第 $i$ 个地区学生所穿制服的颜色记为数字 $i$。

为了组织摆拍，摄影师计划按以下方式进行： 舞台上有一排位置供学生站立，沿舞台从 $1$ 到 $m$ 编号。摄影师计划依次联系某些代表团的负责人，请求该代表团的几名学生上台。他会给出两个数字：$L$ 和 $R$。被选中的代表团学生上台并占据从第 $L$ 个到第 $R$ 个（含）的所有位置。如果这些位置上已经站有其他代表团的学生，他们将离开舞台，而新代表团的学生将占据这些位置。摄影师对每个代表团的负责人最多只能联系一次。

为了使照片色彩和谐，摄影师希望照片上站着 $m$ 名学生，且他们所穿制服的颜色必须严格遵循特定的顺序。现在他想知道如何才能拍出理想的照片。

你需要编写一个程序，根据给定的照片上制服颜色的顺序，确定应按什么顺序请求代表团负责人派学生上台，以及他们应该占据哪些位置才能拍出理想的照片，或者判断这是不可能的。

输入格式

第一行包含两个整数：$m$ 和 $n$ ($1 \leqslant m \leqslant 3 \cdot 10^5$, $1 \leqslant n \leqslant 3 \cdot 10^5$)。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($1 \leqslant a_i \leqslant n$)，即摄影师希望在照片中看到的制服颜色顺序。

输出格式

第一行应包含一个整数 $k$。如果无法拍出理想的照片，该数字应为 $-1$。否则，它应等于摄影师为拍出理想照片所必须联系的代表团负责人数量。

在这种情况下，接下来的 $k$ 行应按摄影师发出请求的顺序描述这些请求。第 $i$ 个请求由三个整数 $c_i, L_i, R_i$ 给出，其中 $c_i$ 是应联系的代表团编号，$L_i$ 和 $R_i$ 分别是该代表团学生需要占据的舞台上第一个和最后一个位置的编号 ($1 \leqslant c_i \leqslant n$，所有 $c_i$ 必须互不相同，$1 \leqslant L_i \leqslant R_i \leqslant m$)。

如果存在多种解决方案，输出其中任意一种即可。

样例

输入 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

子任务