CF643G.Choosing Ads

One social network developer recently suggested a new algorithm of choosing ads for users.

There are n slots which advertisers can buy. It is possible to buy a segment of consecutive slots at once. The more slots you own, the bigger are the chances your ad will be shown to users.

Every time it is needed to choose ads to show, some segment of slots is picked by a secret algorithm. Then some advertisers are chosen. The only restriction is that it should be guaranteed for advertisers which own at least p% of slots composing this segment that their ad will be shown.

From the other side, users don't like ads. So it was decided to show no more than ads at once. You are asked to develop a system to sell segments of slots and choose ads in accordance with the rules described above.

某社交网络开发者最近提出了一种为用户选择广告的新算法。

共有 $n$ 个广告位可供广告主购买。广告主可一次性购买一段连续的广告位。拥有的广告位越多，其广告被展示给用户的概率就越大。

每次需要选择待展示的广告时，一个秘密算法会选定某一段广告位区间。随后从中选择若干广告主。唯一约束条件是：对于该区间内所占广告位比例至少为 $p\%$ 的广告主，必须保证其广告被展示。

另一方面，用户不喜欢过多广告。因此决定：每次最多仅展示 则广告。你需要设计一套系统，用于出售广告位区间，并依据上述规则选择待展示的广告。

The first line of the input contains three integers n, m and p (1 ≤ n, m ≤ 150 000, 20 ≤ p ≤ 100) — the number of slots, the number of queries to your system and threshold for which display of the ad is guaranteed.

Next line contains n integers a__i (1 ≤ a__i ≤ 150 000), where the i-th number means id of advertiser who currently owns the i-th slot.

Next m lines contain queries descriptions. Each description is of one of the following forms:

• 1 l r id (1 ≤ l ≤ r ≤ n, 1 ≤ id ≤ 150 000) — advertiser id bought all slots in a range from l to r inclusive;
• 2 l r (1 ≤ l ≤ r) — you need to choose advertisers for segment [l, r].

输入的第一行包含三个整数 $n$、$m$ 和 $p$（$1 ≤ n, m ≤ 150\,000$，$20 ≤ p ≤ 100$）——分别表示广告位数量、对系统的查询次数，以及保证广告展示的阈值。

第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 150\,000$），其中第 $i$ 个数表示当前拥有第 $i$ 个广告位的广告主编号。

接下来 $m$ 行为查询描述。每条描述属于以下两种形式之一：

• 1 l r id（$1 ≤ l ≤ r ≤ n$，$1 ≤ id ≤ 150\,000$）——广告主 id 购买了区间 $[l, r]$ 内的所有广告位；
• 2 l r（$1 ≤ l ≤ r ≤ n$）——你需要为区间 $[l, r]$ 选择广告主。

For each query of the second type answer should be printed in a separate line. First integer of the answer should be the number of advertisements that will be shown . Next cnt integers should be advertisers' ids.

It is allowed to print one advertiser more than once, but each advertiser that owns at least slots of the segment from l to r should be in your answer.

对于每个第二类查询，答案应单独成行输出。答案的第一个整数为将要展示的广告数量（即 ）。随后的 cnt 个整数为广告主的 ID。

允许在答案中重复输出同一广告主，但凡拥有区间 $[l, r]$ 中至少 个广告位的广告主，其 ID 必须出现在答案中。

Samples demonstrate that you actually have quite a lot of freedom in choosing advertisers.

示例表明，您在选择广告主方面实际上拥有相当大的自由度。