CF643G Choosing Ads

一位社交网络开发人员最近提出了一种为用户选择广告的新算法。 广告商可以购买 $n$ 个时段。他们可以一次性购买一段连续的时段。拥有的时段越多，广告向用户展示的机会就越大。 每次需要选择要展示的广告时，都会通过一种秘密算法选出一些时段，然后再选择一些广告商。然而，要求所有在这个部分拥有至少 $p\%$ 的时段的广告商必须全部被选中。 另一方面，用户不喜欢广告。因此，决定同时显示的广告商数量不得超过 $\lfloor \frac{100}{p} \rfloor$。请您根据上述规则开发一个销售时段段和选择广告商的系统。

输入的第一行包含三个整数 $n,m,p$（$1 \le n,m \le 150000,20 \le p \le 100$）——时段数、系统查询次数和保证广告显示的阈值。 下一行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 150000$），其中第 $i$ 个数字表示当前拥有第 $i$ 个时段的广告商 ID。 接下来的 $m$ 行包含查询描述。每个描述都是以下形式之一： - `1 l r id` $(1 \le l \le r \le n, 1 \le id \le 150000)$：广告商 $id$ 购买了从 $l$ 到 $r$（含）范围内的所有时段； - `2 l r` $(1 \le l \le r)$ - 您需要为段 $[l, r]$ 选择广告商。

对于第二种类型的每个查询，答案应单独打印一行。答案的第一个整数应为将显示的广告数量 $(0 \le cnt \le \lfloor \frac{100}{p} \rfloor)$。接下来的 $cnt$ 个整数应该是广告商的 ID。 允许不止一次打印同一个广告商，但所有至少拥有 $\lceil \frac{p \cdot (r-l+1)}{100} \rceil$ 个在 $l$ 到 $r$ 段插槽的广告商，都应出现在答案中。

样例表明，您在选择广告商时实际上有很大的自由度。