顶级厨师
题号：NC252049
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小Z是一位顶级厨师。

作为一位顶级厨师，小Z掌握n种烹饪方式，其中第i种烹饪方式的熟练度为a_{i}。于此同时，小Z的厨房里常备有m种食材，其中第i种食材的新鲜度为b_{i}。
小Z如果使用第i种烹饪方式烹饪第j种食材，所得到的菜肴具有一种叫做美味值的属性，该属性的计算方式为c_{i,j} = a_{i} \times b_{j}。于此同时，由于食材和烹饪方式的特殊性，有k个烹饪方式+食材的组合是被禁止的。

有一天小Z想知道，他所能烹饪的所有菜肴中，第x小的美味值是多少？由于小Z要忙着烹饪菜肴，所以他把这个艰巨的任务交给了你。注意，由于小Z的好奇心比较强，所以你需要回答他的Q次询问。

输入描述:

第一行包含四个正整数n , m , k,Q (2 \leq n \leq 10^{5}，2 \leq m \leq 10^{5}，2 \leq k \leq \min(10^{6}, n \times m - 1)，1 \leq Q \leq 5)，变量的含义如题意所示。

第二行包含n个正整数a_1,a_2,\ldots,a_n (1\leq a_{i} \leq 10^6)。

第三行包含m个正整数b_1,b_2,\ldots,b_m (1\leq b_i\leq 10^6)。

接下来有k行，每一行包含两个整数u_{i}, v_{i} (1\leq u_{i}\leq n，1 \leq<br /> v_{i} \leq m)。表示食材v_{i}不能用第u_i种烹饪方式进行烹饪。数据保证k个限制互不相同。

接下来有Q行，每行包含一个整数x_i (1\leq x_{i} \leq nm - k)，表示第i次小Z询问第x_{i}小的美味值。

输出描述:

输出Q行，第i行表示第i个询问的答案。
示例1

输入

复制 
4 4 2 2
1 2 3 4
10 20 30 40
1 2
1 3
1
2

输出

复制 
10
20