The continent of Antagarich was colonized slowly. Long ago its northern part was inhabited by the elves of Avlee. Later, the hot southern desert of Bracada was occupied by the white mages. At the same time, necromancers settled in Deyja, a land to the north of Bracada and to the south-west of Avlee. Although white and dark mages didn't really like each other, each group had some artifacts that the other group would be happy to buy. As a result, the trading relationship between Bracada and Deyja grew stronger, and soon the mages built a very busy trade route between these lands.

Erathia was founded later, and at first it was stretched along this route. At that time Erathia's economy was based solely on trading, so new trading guilds appeared all the time. Each of the guilds was present in a few cities which were consecutively situated along the route. Caravans of each guild travelled between all pairs of cities of that guild equally often.

The state's treasury was replenished by fees collected from all the caravans moving along the trade route. There was a fee for each route segment connecting two neighboring cities, and this fee could change over time. For example, the fee could be decreased in the areas of frequent goblin attacks, or increased in the areas with high traffic.

Loins, the royal treasurer, studies Erathia's economy and tries to predict the profit of trade guilds. He wants to know the amount of money paid in fees by each guild. He has a chronologically ordered list of documents that contains all the royal orders changing the fee and all the papers establishing new guilds. This data should be used to calculate the average fee paid by a caravan of a given trade guild.

The first line contains the number n of cities in Erathia and the number m of documents collected by Loins (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). The following m lines describe the documents of two possible types:

• “change a b d”: the fee for travelling along each route segment between cities a and b changed by d gold coins (if d is positive, the fee increased; if d is negative, the fee decreased);
• “establish a b”: a new guild which is present in all cities between a and b was established.

All numbers are integers; 1 ≤ a < b ≤ n; −10 000 ≤ d ≤ 10 000. Cities are numbered in the order they are located along the route: from Bracada to Deyja. The fee for travelling along a segment was never larger than 10 000 gold coins, otherwise merchants would protest. Of course, the fee was always non-negative. Before the first royal order changing the fee, it is equal to zero for all route segments.

After each document establishing the new guild, output in a single line the average amount of fee paid by a caravan of this guild. The absolute or relative error should not exceed 10⁻⁶.