TV Store

Asadullo, the president of Dadorlandtiria, owns a huge TV store. The store carries \(n\) types of TVs, numbered from \(0\) to \(n-1\). A type-\(i\) TV has a screen size of \(w[i] \times h[i]\) pixels and costs \(c[i]\) dador dollars. The store has an unlimited quantity of each type.

\(q\) customers visit Asadullo, numbered from \(0\) to \(q-1\). Customer \(j\) wants to watch a film with aspect ratio \(x[j] : y[j]\), and has \(b[j]\) dador dollars in their wallet.

When a film is played on a TV, it adapts to the screen dimensions while preserving its aspect ratio, and the leftover pixels are filled with black. Naturally, the number of used pixels must be an integer.

For example, if a TV's screen is \(1920 \times 1080\) pixels and the film's aspect ratio is \(20 : 9\), then a \(1920 \times 864\) region of the screen is used, because \(1920 : 864 = 20 : 9\). As another example, if the film's aspect ratio is an unusual value like \(37 : 17\), a \(1887 \times 867\) region of the screen can be used.

Every customer wants to watch their film at the highest possible quality. For each customer, help find a TV they can afford that maximizes the number of used pixels. If no suitable TV exists for them, return \(-1\) as the answer. If several TVs achieve the maximum quality, you may return any of them.

Note that TVs cannot be rotated.

Implementation details

You should implement the following procedure:

int[] best_tv(int n, int[] w, int[] h, int[] c,
              int q, int[] x, int[] y, int[] b)

• \(n\): the total number of TV types.
• \(w\), \(h\), \(c\): arrays of length \(n\) – information about the TVs.
• \(q\): the total number of customers.
• \(x\), \(y\), \(b\): arrays of length \(q\) – information about the customers.
• The procedure should return an array of length \(q\), where element \(j\) is the index of the best TV for customer \(j\).
• This procedure is called exactly once.

Example

Consider the following call:

best_tv(2,
        [1920, 3840],
        [1080, 2400],
        [ 350,  800],
        6,
        [ 20,  37,  16, 1600, 4000,  20],
        [  9,  17,  10, 1000, 4001,   9],
        [500, 350, 900,  900, 1000, 100])

In this example there are two TV types: the type-0 TV has a \(1920 \times 1080\) pixel screen and costs 350 dador dollars. The type-1 TV has a \(3840 \times 2400\) pixel screen and costs 800 dador dollars.

• Customer \(0\) has 500 dador dollars and buys the type-0 TV to watch their \(20 : 9\) film.
• Customer \(1\) has 350 dador dollars and also buys the type-0 TV.
• Customer \(2\) buys the type-1 TV.
• Customer \(3\) also buys the type-1 TV. Note that customers \(2\) and \(3\) have the same amount of money and watch films with the same aspect ratio, because \(16 : 10 = 1600 : 1000\).
• Customer \(4\) has 1000 dador dollars, but unfortunately no TV can display a \(4000 : 4001\) film.
• Customer \(5\) has 100 dador dollars and cannot afford any TV.

Therefore, the procedure should return \([0, 0, 1, 1, -1, -1]\).

Constraints

• \(1 \le n \le 100\,000\)
• \(1 \le q \le 100\,000\)
• \(1 \le w[i], h[i], c[i] \le 10^6\) (for all \(0 \le i < n\))
• \(1 \le x[j], y[j], b[j] \le 10^6\) (for all \(0 \le j < q\))

Subtasks

1. (14 points) \(n, q \le 1000\)
2. (15 points) \(w[i], h[i], x[j], y[j] \le 30\) for all \(i\) and \(j\)
3. (25 points) \(w[i] = h[i]\) for all \(i\)
4. (25 points) \(c[i] = b[j] = 1\) for all \(i\) and \(j\)
5. (21 points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

• line \(1\): \(n\)
• line \(2 + i\) (\(0 \le i < n\)): \(w[i] \; h[i] \; c[i]\)
• line \(2 + n\): \(q\)
• line \(3 + n + j\) (\(0 \le j < q\)): \(x[j] \; y[j] \; b[j]\)

Suppose the best_tv() procedure returns the array \(r\). The sample grader prints the answers in the following format:

• line \(1 + j\) (\(0 \le j < q\)): \(r[j]\)