该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

Muxue youth arrives at the Wind Layer of the Ice Crystal Labyrinth, which is a massive three-dimensional ventilation duct system. Each duct has a fixed airflow capacity limit, and Muxue youth needs to establish a maximum airflow channel from the source to the sink in the network.

This duct system has a special property: some ducts have a "bidirectional regulation" function, where their airflow direction can be dynamically changed, but the total flow is limited. Additionally, the connection points (nodes) between ducts also have capacity limits, and each node can only pass a certain amount of airflow.

Given a three-dimensional airflow network with $n$ nodes and $m$ ducts, the network has the following characteristics:

1. Node Capacity
   Each node $i$ has a capacity $c_i$, representing the maximum total airflow that can pass through the node per unit time.

2. Duct Properties
   Each duct connects two nodes $u$ and $v$, with:

   • Base capacity $cap$: The maximum airflow that can pass per unit time.
   • Adjustment coefficient $k$ ($0 \leq k \leq 1$): If airflow flows from $u$ to $v$, the actual available capacity is $cap \times k$; if from $v$ to $u$, the actual available capacity is $cap \times (1-k)$.
   • Maintenance status $s$ (0 or 1): $s=1$ indicates the duct is under maintenance and can only pass 50% of its original capacity.

3. Special Rules

   • Airflow must satisfy flow conservation (except at the source and sink).
   • The total flow passing through a node cannot exceed its capacity.
   • The actual capacity of each duct is:
     $\min(cap \times factor \times (s==1 \ ? \ 0.5 : 1), \text{remaining node capacity})$

Now, given the source $S$ and sink $T$, along with $q$ operations and queries: (1) Update operation: Change the maintenance status $s$ of a duct. (2) Query operation: Ask for the maximum flow from $S$ to $T$ in the current network.

You need to process all operations and queries.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 5$), indicating the number of test cases.

The format for each test case is as follows:

1. The first line contains four integers $n, m, S, T$ ($2 \leq n \leq 500$, $1 \leq m \leq 5000$, $1 \leq S, T \leq n$, $S \neq T$).
2. The second line contains $n$ integers $c_1, c_2, ..., c_n$ ($0 \leq c_i \leq 10^9$).
3. The next $m$ lines each contain four integers $u, v, cap, k$ ($1 \leq u, v \leq n$, $u \neq v$, $1 \leq cap \leq 10^9$, $0 \leq k \leq 100$; the actual $k$ value is the input value divided by 100).
4. The next line contains an integer $q$ ($1 \leq q \leq 1000$).
5. The next $q$ lines each represent an operation or query:
   • Operation: 1 x means toggling the maintenance status of duct $x$ ($1 \leq x \leq m$).
   • Query: 2 means asking for the current maximum flow.

Note: Initially, the maintenance status $s=0$ for all ducts.

Output Format

For each query, output a real number on a line, representing the current maximum flow, accurate to six decimal places.

If the source cannot output or the sink cannot input due to node capacity limitations, output "0.000000".

Sample Input

1
4 5 1 4
10 5 8 12
1 2 8 50
1 3 6 30
2 3 4 70
2 4 10 20
3 4 7 60
5
2
1 3
2
1 5
2

Sample Output

5.800000
5.200000
4.100000

Sample Explanation

Initial state:

• Duct 1: 1→2 capacity 8×0.5=4.0, 2→1 capacity 8×0.5=4.0
• Duct 2: 1→3 capacity 6×0.3=1.8, 3→1 capacity 6×0.7=4.2
• Duct 3: 2→3 capacity 4×0.7=2.8, 3→2 capacity 4×0.3=1.2
• Duct 4: 2→4 capacity 10×0.2=2.0, 4→2 capacity 10×0.8=8.0
• Duct 5: 3→4 capacity 7×0.6=4.2, 4→3 capacity 7×0.4=2.8

After considering node capacity limitations, calculate the maximum flow.

Data Range and Constraints

Subtask 1 (20 points)

• $n \leq 50$, $m \leq 200$, $q \leq 50$, all $k=50$

Subtask 2 (30 points)

• $n \leq 200$, $m \leq 1000$, $q \leq 200$, no node capacity limitations (all $c_i = \infty$)

Subtask 3 (30 points)

• $n \leq 300$, $m \leq 3000$, $q \leq 500$

Subtask 4 (20 points)

• No additional restrictions

For all data

• $1 \leq T \leq 5$
• The total sum of $n \times q$ across all test cases does not exceed $10^6$
• The total sum of $m \times q$ across all test cases does not exceed $5 \times 10^6$
• Capacities and coefficients may result in a maximum flow of 0
• High output precision is required; it is recommended to use double and retain sufficient decimal places

Hint

1. This is a maximum flow problem with node capacities.
2. Node capacities can be handled by splitting each node into an incoming node and an outgoing node.
3. Dynamic modifications require efficient updates to the maximum flow.
4. Consider using the Dinic algorithm or the ISAP algorithm.