时间限制： 1.0 秒

空间限制： 512 MB

题目描述

你有一块长度为 $n$ 的木板和 $m$ 种颜色，木板被平均分成 $n$ 段，分别编号为 $1, 2, \cdots, n$。第 $i$ 段被染为颜色 $c_i$。这块木板为 $1$ 号木板。

你要进行 $k$ 次切割操作，第 $i~(1 \le i \le k)$ 次切割操作有三个参数 $x_i, l_i, r_i$：

• 表示将 $x_i$ 号木板中编号在 $[l_i, r_i]$ 之间的所有段切割下来，作为第 $i + 1$ 号木板；
• 原先木板切割剩下的部分重新连接成一块木板，木板编号仍为 $x_i$；
• 每一段的编号不受切割操作影响；
• 特别的，木板长度可以为 $0$，即切下的木板不包含任一段。

你想要知道，每次切割操作切下的木板：

1. 包含多少种不同的颜色？
2. 包含多少个颜色段？

一个颜色段定义为：一块木板上极长的连续若干段，满足这些段具有相同的颜色。若切下的木板长度为 $0$，则不同颜色数和颜色段数都视为 $0$。

输入格式

从标准输入读入数据。

输入共 $k+2$ 行。

第一行包含三个正整数 $n, m, k$。

第二行包含 $n$ 个正整数 $c_1, c_2, \cdots, c_n$，表示木板上每一段的颜色。

接下来共有 $k$ 行，每行三个整数 $x_i, l_i, r_i$，表示一次切割操作。

输出格式

输出到标准输出。

共 $k$ 行，第 $i$ 行两个正整数分别表示第 $i$ 次切下的木板中不同颜色数和颜色段数。

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

2 2
1 1
0 0
2 2
1 1

样例 1 解释

初始 $1$ 号木板包含段 $(1,2,3,4,5,6)$，颜色序列为 $(1,2,2,3,1,2)$。

第一次切割操作，切下 $1$ 号木板上段落编号在 $[3,4]$ 的部分，作为 $2$ 号木板：

• $2$ 号木板包含段 $(3,4)$，其颜色序列为 $(2,3)$；
• $1$ 号木板剩余段 $(1,2,5,6)$，其颜色序列为 $(1,2,1,2)$。

第二次切割操作，切下 $1$ 号木板上段落编号在 $[5,5]$ 的部分，作为 $3$ 号木板：

• $3$ 号木板包含段 $(5)$，其颜色序列为 $(1)$；
• $1$ 号木板剩余段 $(1,2,6)$，其颜色序列为 $(1,2,2)$。

第三次切割操作，切下 $1$ 号木板上段落编号在 $[4,5]$ 的部分，作为 $4$ 号木板：

• 因为 $1$ 号木板上已经不含段 $4$ 和 $5$，新切下的 $4$ 号木板为空；

第四次切割操作，切下 $1$ 号木板上段落编号在 $[1,6]$ 的部分，作为 $5$ 号木板：

• $5$ 号木板包含段 $(1,2,6)$，其颜色序列为 $(1,2,2)$；
• $1$ 号木板剩余部分为空。

第五次切割操作，切下 $2$ 号木板上段落编号在 $[4,4]$ 的部分，作为 $6$ 号木板：

• $6$ 号木板包含段 $(4)$，其颜色序列为 $(3)$；
• $2$ 号木板剩余段 $(3)$，其颜色序列为 $(2)$。

子任务

全部的数据满足：

• $1 \le n, m, k \le 10^{5}$；
• $1 \le c_i \le m$；
• $1 \le l_i \le r_i \le n$；
• $1 \le x_i \le i$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 特殊性质 A：$r_i - l_i \le 1000$；
• 特殊性质 B：$c_i = i$；
• 特殊性质 C：对于所有的 $1 \le i < j \le n$ 满足 $c_i \le c_j$。