Problem Description

Today, Scarlet had the privilege of witnessing a unique OI training session in the computer room. Due to some marvelous Special Judge (SPJ), all participants' scores were positive real numbers (with no upper limit).

When a player A's score is at least $k$ times (where $k > 0$) the score of player B, we say that player A $k$ times kills player B, and player B is $k$ times killed by player A.

Even more exciting is that before the training, many players set flags such as "If I don't $k$ times kill player X, I will cross-dress," or "If player Y $k$ times kills me, I will cross-dress."

Knowing the truth, the conscientious coach Patchouli decided to relax the restrictions on the flags to maintain order in the computer room. Patchouli set a positive constant $T$. A player who set a flag like "If I don't $k$ times kill player X, I will cross-dress" only needs to successfully $k - T$ times kill player X to avoid cross-dressing. Similarly, a player who set a flag like "If player Y $k$ times kills me, I will cross-dress" only needs to avoid being successfully $k + T$ times killed by player Y to avoid cross-dressing.

Scarlet, who knew some players' scores and specific flags in advance, couldn't bear to see such a wonderful competition without anyone cross-dressing. To facilitate negotiations with Patchouli, Scarlet wants to determine the maximum real number $T$ such that there will definitely be a player who has to cross-dress after the competition.

Input Format

The first line contains three integers $n, s, t$, representing the number of players in the computer room, the total number of flags set by players, and the number of players whose scores Scarlet knows, respectively. The $n$ players are numbered from 1 to $n$, referred to as player $k$.

The next $s$ lines each contain four integers $o, A, B, k$. If $o = 1$, it means player A set a flag "If I don't $k$ times kill player B, I will cross-dress." If $o = 2$, it means player A set a flag "If player B $k$ times kills me, I will cross-dress."

The next $t$ lines each contain two integers $C, x$, indicating that Scarlet knows player $C$'s score is $x$.

Output Format

If there exists a maximum $T$ that guarantees a player will cross-dress after the competition, output $T$, provided that the absolute error of the output from the answer does not exceed $10^{-4}$.

If no such $T$ exists, output -1.

Sample Input and Output

Sample Input #1

3 5 1
1 2 1 2
1 3 2 2
1 3 1 4
2 1 2 2
2 1 3 4
1 1

Sample Output #1

-1

Sample Input #2

3 2 3
1 2 1 10
2 2 3 6
1 1
2 6
3 9

Sample Output #2

3.9999993984

Notes

• For $30\%$ of the data, $n \leq 5$, $s \leq 2$;
• For another $40\%$ of the data, it is guaranteed that $t = n$;
• For $100\%$ of the data, $1 \leq n, s \leq 1000$, $1 \leq A, B, C, t \leq n$, $1 \leq k \leq 10$, $1 \leq x \leq 10^9$. It is guaranteed that the $C$ values in the input are all distinct.

见题面 Input 部分

见题面 Output 部分