По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.
Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?
Формат входных данных
Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)
• G l r i - Геральд переставляет кружки с l по r в позицию I (1 <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)
• L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)
• E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)
Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер.
Изначально в кружках по 0 литров.
Формат выходных данных
На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес.
|
Пример входных данных |
Пример выходных данных |
5 7
L 2 5 10
G 1 3 5
L 1 4 3
L 3 3 4
E 2 3 2
E 2 2 4
E 5 5 15
15 |
13 4 2 13 15
2 15
|
5 6
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
10 |
5 1 2 3 4
4 10 |
5 8
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
G 1 1 6
G 1 5 1
10 |
1 2 3 4 5
4 10 |
Пояснения к 1 примеру
1. 0 10 10 10 10
2. 10 0 10 10 10
3. 13 3 13 13 10
4. 13 3 17 13 10
5. 13 2 2 13 10
6. 13 4 2 13 10
7. 13 4 2 13 15
Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.
Пояснения к 3 примеру
1. 1 0 0 0 0
2. 1 2 0 0 0
3. 1 2 3 0 0
4. 1 2 3 4 0
5. 1 2 3 4 5
6. 5 1 2 3 4
7. 1 2 3 4 5
8. 1 2 3 4 5
Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.
(с) Аксенов Владимир 10и