K-Koishi in Wetland Park_第四届南方科技大学程序设计竞赛同步赛

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

The Wetland Park in SUSTech has long been a mysterious and fascinating place to visit. Satori's little sister Koishi was attracted but unfortunately lost her way inside the park, so she called Satori for help.

There are $N(2\leq N\leq 100)$ viewing decks in the park, which are connected by $M(N-1\leq M\leq \frac{N\times(N-1)}{2} )$ plank roads build in the wetland park with some magical lychee trees growing alongside.

Initially the fruits along the $i^{th}$ road can be described by a pair $(A_i,B_i) (1\leq A_i,B_i\leq 10^8)$ , and Koishi will eat $A_i$ juicy lychees when she passes through the $i^{th}$ road.

Yet, each time Koishi passes through one road, the lychee trees along every road will change from $(A_j,B_j)$ to $(B_j,A_j \bmod B_j)$ unless its original $B_j=0$ (If $B_j=0$ , the pair $(A_j,B_j)$ will not change).

The sad truth is that Koishi is completely lost. Thus, she will randomly choose to start her journey from viewing deck $i(1\leq i\leq N-1)$ with probability $\frac{P_i}{\sum _{i=1} ^{N-1} P_i} (1\leq P_i\leq 10^6)$ . When she is at viewing deck $i$ , she will choose to walk through one plank road connecting it with equal probability. Satori is waiting for her at viewing deck $N$ . Boring as she is, she starts to calculate the expected number of lychees her little sister would eat before she reaches viewing deck $N$ .

As Satori is a master in Probability, she would change some of $P_i$ or pair $(A_j,B_j)$ . Formally, she will perform $Q (0\leq Q\leq 10^5)$ changes, for the $k^{th}$ one, she would first tell you the operation type $opt_k$ , then

If $opt_k=1$ , Satori will choose a viewing deck $x$ and change $P_x$ to $val(1\leq x\leq N,1\leq val\leq 10^6)$

If $opt_k=2$ , Satori will choose a road $u$ and change $(A_u,B_u)$ to $(a, b) (1\leq u\leq M, 1\leq a, b\leq 10^8)$

As Satori is quite lazy, the total number of the first operation will not exceed 100.

Also, as Satori is a master in Cryptology, she would make her problem even more difficult by performing $\oplus$ operation on her previous answer. Formally, if the answer after her last change is $res$ , then

If $opt_k=1$ and you receive $x,val$ , her actual changes will be: $x=((x\oplus res) \bmod (N-1)) +1$ and $val=((val \oplus res) \bmod 10^6)+1$

If $opt_k=2$ and you receive $u,a,b$ , her actual changes will be $u=((u\oplus res) \bmod M)+1,a=((a\oplus res) \bmod 10^8)+1 ,b=((b\oplus res) \bmod 10^8)+1$

Here $\bmod$ means module operator and $\oplus$ means exclusive or (XOR) operator.

Note that before Satori's first change $res=0$ , and the changes Satori made are accumulative.

输入描述:

The first line contains three integers .
The second line contains  integers .
The next  lines each contain four integers , indicating the  road connects deck  and  and has pair. Note that the roads are numbered from 1 to .
The next  lines each has one of the two following formats:
    
    
Note that the graph is connected, and the total number of the first operation will not exceed 100.