SOLVE
LATER
Given an undirected-weighted graph of \(N\) vertices, numbered from \(1\) to \(N\). Initially, there is no edge in the graph. There is a chip places on some vertex. At each second, the chip randomly moves to one of its neighbors with probability relative with the weight of that edges, if it has no neighbor, the chip won't move. For example, assume that the chip is on vertex \(1\) and there are three edges \((1, 2)\) weight \(1\), \((1, 3)\) weight \(2\) and \((1, 4)\) weight \(3\). Then the chip moves to vertex \(2\) with probability \(\frac{1}{1 + 2 + 3}\), vertex \(3\) with probability \(\frac{2}{1 + 2 + 3}\), vertex \(4\) with probability \(\frac{3}{1 + 2 + 3}\); at the next second. You are asked to process \(Q\) queries:
Input Format
The first line contains two integers \(N, Q\) denoting the number of vertices of the graph and the number of queries.
Each of \(Q\) following lines contains a query of two kinds as described above.
Output Format
For each query of the second type, assume \(x\) is the answer, you should print \(floor(x\times 10^9 + \frac{1}{2})\) (the largest integer doesn't exceed \(x\times 10^9 + \frac{1}{2}\)) in a line. (It is guaranteed that the output doesn't change if we change \(x\) by \(x + 10^{-18}\) or \(x - 10^{-18}\))
Constraints
The actual answer for \(2\)nd query is \(0\).
The actual answer for \(5\)-th query is \(\frac{1}{3} + \epsilon\), where \(|\epsilon| < 10^{-100}\).