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$ 段的插槽，都应出现在答案中。

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