Как известно, континент Антагарич заселялся постепенно. Издревле на самом севере жили эльфы АвЛи. Много позднее в жаркой южной пустыне Бракады обосновались светлые маги. Примерно в то же время на севере от Бракады и на юго-западе от АвЛи, в Дейе обосновались некроманты. И хотя светлые и тёмные маги друг друга недолюбливали, порой у одних находились артефакты, интересные другим. Поэтому со временем торговля между Бракадой и Дейей расширялась, и в какой-то момент между ними был проложен торговый тракт, который вскоре стал очень оживлённым.

Эрафия появилась позже и некоторое время целиком располагалась вдоль этого тракта. Изначально Эрафия была торговым государством, и новые торговые гильдии появлялись в больших количествах. Каждая из гильдий охватывала своей деятельностью несколько подряд идущих вдоль тракта городов. При этом караваны одной гильдии одинаково часто ходили между всеми парами городов, в которых она вела свою деятельность.

Основным источником дохода государства были пошлины, которые взимались со всех караванов, перемещающихся вдоль торгового тракта. Пошлина взималась отдельно за каждый отрезок тракта между двумя соседними городами и могла меняться со временем — например, понижалась в тех районах, где начинались нападения гоблинов, или увеличивалась там, где тракт был перегружен.

Лоинс, королевский казначей, изучая экономику Эрафии этого периода, пытается оценить прибыльность торговых гильдий. Для этого ему нужно знать, сколько денег отдавала государству в качестве пошлины каждая гильдия. Он выписал в хронологическом порядке все королевские указы об изменении пошлины и все факты основания новых гильдий. Этих данных должно хватить, чтобы найти среднюю величину пошлины, уплаченной одним караваном торговой гильдии.

В первой строке записаны целые числа n и m — количество городов в Эрафии и количество событий, выписанных Лоинсом, соответственно (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). В следующих m строках записаны события двух видов:

• «change a b d» — пошлина за проезд по каждому из отрезков тракта между городами a и b изменилась на d золотых монет (увеличилась, если d положительно, и уменьшилась, если d отрицательно);
• «establish a b» — основана торговая гильдия, которая ведёт свою деятельность во всех городах от a до b включительно.

Числа a, b и d целые; 1 ≤ a < b ≤ n; −10 000 ≤ d ≤ 10 000. Города пронумерованы в порядке их расположения вдоль тракта: от Бракады до Дейи. Пошлина за проезд ни по какому отрезку тракта никогда не поднималась выше 10 000 золотых монет, поскольку иначе торговцы подняли бы бунт. Ну и, естественно, пошлина никогда не опускалась ниже нуля. До первого указа об изменении пошлины она не взималась ни с одного отрезка тракта.

На каждое из событий основания гильдии выведите в отдельной строке среднюю величину пошлины, которую в этот момент платила эта гильдия с одного своего каравана, с абсолютной или относительной погрешностью не более 10⁻⁶.