Tích ưu tiên
Cho hai dãy số nguyên \((a): a_1, a_2, ...,a_m\) và \((b): b_1, b_2, ..., b_n\). Với mỗi truy vấn dạng \(u\:v\) bạn cần phải tìm giá trị nhỏ nhất và lớn nhất trong tất cả các tích dạng \(a_i*b_j\) với \(1 \le i \le u\) và \(1 \le j \le v\). Nói cách khác với mỗi \(u\:v\) bạn cần tính giá trị của \(\displaystyle\max_{\substack{1 \le i \le u\\1 \le j \le v}}\{a_i*b_j\}\) và \(\displaystyle\min_{\substack{1 \le i \le u\\1 \le j \le v}}\{a_i*b_j\}\).
Đầu vào
Dòng đầu gồm ba số nguyên dương \(m\), \(n\) và \(q\) \((1 \le m, n, q \le 10^5)\), số phần tử của dãy \((a)\), \((b)\) và số truy vấn.
Dòng thứ hai gồm \(m\) số nguyên là các phần tử của dãy \((a)\) có giá trị tuyệt đối không vượt quá \(10^9\).
Dòng thứ ba gồm \(n\) số nguyên là các phần tử của dãy \((b)\) có giá trị tuyệt đối không vượt quá \(10^9\).
\(q\) dòng cuối mỗi dòng chứa hai số dương \(u, v\) \((1 \le u \le m, 1 \le v \le n)\).
Đầu ra
\(q\) dòng, mỗi dòng gồm hai số nguyên (số lớn hơn đứng trước) là trả lời của một truy vấn.
Subtask
\(30\%\) số test có \(q = 1, u = m, v = n\).
Ví dụ
Đầu vào:
6 6 3
-1 2 -3 4 -5 6
1 -2 3 -4 5 -6
1 6
2 5
3 4
Đầu ra:
6 -5
10 -8
12 -9
Comments