Determining the Maximum T for Guaranteed Cross‐dressing

In a unique OI training session, every contestant finishes with a positive score (with no upper limit) due to some unusual SPJ. We say that contestant A \(k\times kills\) contestant B if A's score is at least \(k\) times B's score. In other words, if contestant A has score \(S_A\) and contestant B has score \(S_B\), then A \(k\times kills\) B if and only if \(S_A \ge k \times S_B\).

Before the contest, several contestants set personal flags. A flag can be of one of two types:

• Type 1 (self-assertion): "If I do not \(k\times kill\) contestant X, then I will cross-dress." However, coach Patchouli relaxes this by saying that if the contestant manages to \((k-T)\times kill\) contestant X, then they are safe.
• Type 2 (threat): "If contestant Y \(k\times kills\) me, then I will cross-dress." Again, coach Patchouli relaxes it by stating that if contestant Y fails to \((k+T)\times kill\) the contestant, then the contestant is safe.

Formally, let \(T\) be a positive real constant chosen by Patchouli. For a contestant who declared a Type 1 flag with parameters \(A\) (the flag setter), target contestant \(X\) and constant \(k\), the contestant avoids cross‐dressing if and only if

[ S_A \ge (k - T) \times S_X. ]

For a contestant who declared a Type 2 flag with parameters \(Y\) (the threatening contestant), target contestant \(A\) (the flag setter) and constant \(k\), the contestant avoids cross‐dressing if and only if

[ S_Y < (k + T) \times S_A. ]

Thus, a flag forces the contestant to cross-dress if the corresponding condition is not met. Rearranging the inequalities:

• For a Type 1 flag: the flag forces cross-dressing if \(S_A < (k - T)S_X\), i.e. if and only if \[ T < k - \frac{S_A}{S_X}. \]
• For a Type 2 flag: the flag forces cross-dressing if \(S_Y \ge (k + T)S_A\), i.e. if and only if \[ T \le \frac{S_Y}{S_A} - k. \]

Given the scores of \(n\) contestants and the details of all flags, your task is to determine the largest real number \(T\) such that after the contest at least one flag will be forced (i.e. at least one contestant must cross-dress). Note that if a flag of Type 1 has a critical value \(k - S_A/S_X\), it forces cross-dressing for any \(T\) strictly less than that value, while a Type 2 flag forces cross-dressing for any \(T\) not greater than \(S_Y/S_A - k\).

The overall answer is the supremum of all \(T\) values for which at least one flag forces cross-dressing. In other words, if we define:

• For each Type 1 flag with parameters \(A, X, k\): define \(f = k - \frac{S_A}{S_X}\). This flag forces cross-dressing if and only if \(T < f\).
• For each Type 2 flag with parameters \(Y, A, k\): define \(f = \frac{S_Y}{S_A} - k\). This flag forces cross-dressing if and only if \(T \le f\).

Your task is to output the largest \(T\) (to 6 decimal places) for which there is at least one flag that forces cross-dressing. If no positive \(T\) can force any flag (i.e. if the maximum critical value \(\le 0\)), output -1.

inputFormat

The input begins with three integers \(n\), \(m_1\), and \(m_2\), where \(n\) is the number of contestants, \(m_1\) is the number of Type 1 flags, and \(m_2\) is the number of Type 2 flags.

The second line contains \(n\) positive real numbers: \(S_1, S_2, \dots, S_n\), representing the scores of the contestants.

Then follow \(m_1\) lines, each containing a Type 1 flag in the format:

A X k

Here, A and X (1-indexed) are the indices of the contestants, and \(k\) is a positive real number.

Then follow \(m_2\) lines, each containing a Type 2 flag in the format:

Y A k

Here, Y and A (1-indexed) are the indices of the contestants, and \(k\) is a positive real number.

It is guaranteed that \(m_1 + m_2 \ge 1\).

outputFormat

Output the largest real number \(T\) (rounded to 6 decimal places) such that at least one flag forces the contestant to cross-dress. If no positive \(T\) can achieve this, output -1.

sample

3 2 1
100 50 10
1 2 2.0
2 3 5.0
1 3 3.0

7.000000