| VK Cup 2016 - Раунд 3 |
|---|
| Закончено |
Один разработчик социальной сети недавно предложил новый алгоритм выбора рекламных объявлений для показа пользователям.
Рекламодателям доступно n слотов, которые они могут купить. За один раз можно выкупить некоторый отрезок слотов. Причём чем больше длина отрезка, тем больше вероятность того, что рекламу покажут пользователю.
Каждый раз, когда решается, какую рекламу показать, секретным образом генерируется некоторый отрезок слотов. Далее выбираются некоторые рекламодатели, чья реклама будет показана. Причем если рекламодатель владеет хотя бы p% всех слотов на этом отрезке, то его рекламу точно покажут.
С другой стороны пользователям не нравится, когда им показывают много рекламы. Поэтому было решено не показывать больше 
рекламных объявлений за раз. Вам предлагается помочь разработать систему, выбирающую рекламу в соответствии с описанным алгоритмом.
В первой строке входных данных содержатся три целых числа n, m и p (1 ≤ n, m ≤ 150 000, 20 ≤ p ≤ 100) — количество рекламных слотов, количество запросов, которые поступили вашей системе, и порог, при котором обязательно показать объявление рекламодателя.
В следующей строке содержатся n целых чисел ai (1 ≤ ai ≤ 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) — необходимо выбрать рекламодателей для отрезка [l, r].
Для каждого запроса второго типа в отдельной строке нужно вывести любой подходящий набор рекламных объявлений. Вначале должно быть записано количество объявлений, которые будут показаны 
, а затем cnt номеров рекламодателей.
Разрешается выводить одного и того же рекламодателя несколько раз, но каждый рекламодатель, который владеет хотя бы 
слотами на отрезке с l по r, должен присутствовать в ответе.
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
3 1 2 3
2 1 3
2 2 1
3 1 1000 1000
1 5
2 5 3
2 1 5
Пример из условия демонстрирует, что у вас есть достаточно большая свобода в выборе рекламодателей.
