一位社交网络开发人员最近提出了一种为用户选择广告的新算法。
广告商可以购买 n 个广告位。可以一次购买一段连续的插槽。您拥有的广告位越多,您的广告向用户展示的机会就越大。
每次需要选择要展示的广告时,都会通过秘密算法选择某些时段。然后选择一些广告商。唯一的限制是,应保证拥有构成该细分市场的至少 p% 的广告位的广告商将展示其广告。
从另一方面来看,用户不喜欢广告。因此,我们决定一次最多展示 $$\left\lfloor \frac{100}{p} \right\rfloor$$ 广告。您需要开发一个系统来销售老虎机片段并根据上述规则选择广告。
输入
输入的第一行包含三个整数 n、m 和 p (1 ≤ n, m ≤ 150 000, 20 ≤ p ≤ 100) - 广告位数量、系统查询数量以及保证广告展示的阈值。
下一行包含n个整数ai (1 ≤ ai ≤ 150 000),其中第i个数字表示当前拥有第i个广告位的广告商的id。
接下来的 m 行包含查询描述。每个描述均采用以下形式之一:
- 1 l r id (1 ≤ l ≤ r ≤ n, 1 ≤ id ≤ 150 000) — 广告客户 id 购买了从 l 到 r 范围内的所有广告位;
- 2 l r (1 ≤ l ≤ r) - 您需要为分段 [l, r] 选择广告客户。
输出
对于第二类型的每个查询,答案应打印在单独的行中。答案的第一个整数应该是将显示的广告数量 $$(0 \leq cnt \leq \lfloor \frac{100}{p} \rfloor)$$。接下来的 cnt 整数应该是广告商的 ID。
允许多次打印一个广告客户,但至少拥有 $$\left\lceil \frac{p \cdot (r - l + 1)}{100} \right\rceil$$ 从 l 到 r 的段的广告客户应该在您的答案中。
示例
输入 #1
5 9 33 1 2 1 3 3 2 1 5 2 1 5 2 1 3 2 3 3 1 2 4 5 2 1 5 2 3 5 1 4 5 1 2 1 5
输出 #1
3 1 2 3 2 1 3 2 2 1 3 1 1000 1000 1 5 2 5 3 2 1 5
注意
示例表明您在选择广告商方面实际上有很大的自由度。