Return - MarisaOJ: Marisa Online Judge
The witch M lives in a country with $n$ cities and $m$ bidirectional roads connecting them. Her house is in city $1$. The country gets a lot of rain, and roads with elevation which does not exceed the rainwater level will be flooded.
In the next $Q$ days, M will tell you her location and the rainwater level $p$ for that day.
She has a car that cannot pass through flooded roads.
She can get out of the car and walk across a flooded road at any time, but the car will be left behind and cannot be used anymore.
Note that the car will return to her starting position the next day, and she cannot use the car left behind on previous days.
She doesn't like walking in the rain at all, so for each day, find a solution to minimize the total **walking** distance on the way home.
### Input
- The first line is an integer $T$, the number of test cases.
- The first line of each test case consists of two integers $n,m$.
- The next $m$ lines, each line contains four integers $u,v,l,a$, indicating a road of length $l$ between $u$ and $v$ with an elevation of $a$.
- The next line contains three integers $Q,K,S$:
+ $Q$ is the number of days.
+ $K$ is the parameter explained below.
+ $S$ is the maximum water level in the upcoming days.
- The next $Q$ lines, each line contains two integers $p_0,v_0$. The $i$-th line represents the $i$-th day:
+ The starting point of that day is $v=(v_0 + K \times \text{lastans} - 1) \mod n + 1$.
+ The water level for that day is $p=(p_0+ K \times \text{lastans}) \mod (S+1)$.
+ $\text{lastans}$ is the answer from the previous day. For the first day, we assume $\text{lastans}=0$.
+ $1 \le v_0 \le n, 0 \le p_0 \le S$.
- All numbers on the same line are separated by spaces.
### Output
- Print $Q$ lines, where the $i$-th line is the answer for the $i$-th day.
### Example
Input:
```
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
```
Output:
```
0
50
200
50
150
```
Explanation
- On the first day, there is no rain, so M can drive home.
- The water level on days $2,3,4$ is the same, causing the flooding of the roads connecting $1,2$ and $3,4$.
- On the second day, there is no alternative but to walk.
- On the third day, walking is the only option as well.
- On the fourth day, M can drive to city $2$ and then walk.
- On the fifth day, all roads are flooded, so M has to get out of the car and walk.
Input 2:
```
1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0
```
Output2:
```
0
2
3
1
```
Explanation:
- Online processing is mandatory.
- The answer for the first day is $0$, so on the second day, we have $v=(5+0-1) \mod 5 + 1 = 5$ and $p=(2+0) \mod (3 + 1) = 2$.
- The answer for the second day is $2$, so on the third day, we have $v=(2 + 2 -1) \mod 5 + 1 = 4$ and $p=(0+2) \mod (3 + 1) = 2$.
- The answer for the third day is $3$, so on the fourth day, we have $v=(4 + 3 - 1) \mod 5 + 1 = 2$ and $p=(0 + 3) \mod (3 + 1) = 3$.
### Constraints
It is guaranteed that for each test case, the following conditions are satisfied:
- $1 \le T \le 3$.
- For each dataset, ensure:
+ $1 \le n \le 2 \times 10^5$.
+ $1 \le m \le 4 \times 10^5$.
+ $K \in \\{0,1\\}$.
+ $1 \le S \le 10^9$.
+ For each edge: $1 \le l \le 10^4, 1 \le a \le 10^9$.
+ There exists a path between any two cities.
Explanation of the conditions in the table:
- For each test of the graph type "tree" or "chain", it is guaranteed $m = n-1$:
+ Tree: Ensure the given graph is a tree.
+ Chain: Ensure $u + 1 = v$.
- Elevation: If this value is $1$ in these tests, ensure $a=1$.
- Online processing: For tests marked as "Yes," ensure $K=1$, otherwise, $K=0$.
| $n$ |
$m$ |
$Q =$ |
Test |
Graph form |
Elevation |
Online processing |
| $\leq 1$ |
$\leq 0$ |
$0$ |
$1$ |
No constraint |
$1$
| No |
| $\leq 6$ |
$\leq 10$ |
$10$ |
$2$ |
| $\leq 50$ |
$\leq 150$ |
$100$ |
$3$ |
| $\leq 100$ |
$\leq 300$ |
$200$ |
$4$ |
| $\leq 1500$ |
$\leq 4000$ |
$2000$ |
$5$ |
| $\leq 200000$ |
$\leq 400000$ |
$100000$ |
$6$ |
| $\leq 1500$ |
$= n - 1$ |
$2000$ |
$7$ |
Chain |
No constraint |
| $8$ |
| $9$ |
| $\leq 200000$ |
$100000$ |
$10$ |
Tree |
| $11$ |
Yes |
| $\leq 400000$ |
$12$ |
No constraint |
No |
| $13$ |
| $14$ |
| $\leq 1500$ |
$\leq 4000$ |
$2000$ |
$15$ |
Yes |
| $16$ |
| $\leq 200000$ |
$\leq 400000$ |
$100000$ |
$17$ |
| $18$ |
| $400000$ |
$19$ |
| $20$ |
Topic
Graph
Tree
Data structure
DSU
Rating
2400
Solution (0)
Solution
