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:

• \(1\ u\ v\ w\): add an edge \((u, v)\) with weight \(w\), there is no multiple edge or self-loop in the graph at any moment.
• \(2\ u\ v\): find the probability the chip is on vertex \(u\) after \(10^{10^{10^{10}}}\) seconds if at the beginning, we place the chip on vertex \(v\).

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

• \(1 \le N, Q \le 10^6\)
• \(1 \le u, v \le n\)
• \(1 \le w \le 10^4\)