CF500D New Year Santa Network

New Year is coming in Tree World! In this world, as the name implies, there are $ n $ cities connected by $ n-1 $ roads, and for any two distinct cities there always exists a path between them. The cities are numbered by integers from 1 to $ n $ , and the roads are numbered by integers from $ 1 $ to $ n-1 $ . Let's define $ d(u,v) $ as total length of roads on the path between city $ u $ and city $ v $ . As an annual event, people in Tree World repairs exactly one road per year. As a result, the length of one road decreases. It is already known that in the $ i $ -th year, the length of the $ r_{i} $ -th road is going to become $ w_{i} $ , which is shorter than its length before. Assume that the current year is year $ 1 $ . Three Santas are planning to give presents annually to all the children in Tree World. In order to do that, they need some preparation, so they are going to choose three distinct cities $ c_{1} $ , $ c_{2} $ , $ c_{3} $ and make exactly one warehouse in each city. The $ k $ -th ( $ 1

The first line contains an integer $ n $ ( $ 3

Output $ q $ numbers. For each given change, print a line containing the expected cost needed to build the network in Tree World. The answer will be considered correct if its absolute and relative error doesn't exceed $ 10^{-6} $ .

Consider the first sample. There are 6 triples: $ (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) $ . Because $ n=3 $ , the cost needed to build the network is always $ d(1,2)+d(2,3)+d(3,1) $ for all the triples. So, the expected cost equals to $ d(1,2)+d(2,3)+d(3,1) $ .