题目描述

小明得到了很多重量不一的牛奶作为奖品。它们是有序的，不过被排成了两列。也就是说，两列牛奶分别按重量从轻到重排列。

现在小明想知道，如果他从两列中各取一段连续位置上的牛奶，把它们重新排成有序的一列，这一列中第 $k$ 轻的牛奶重量为多少。

输入格式

第一行两个正整数 $n,m$，分别表示两列牛奶的数量；

第二行 $n$ 个非严格升序排列的正整数 $a_i$，表示第一列中每瓶牛奶的重量；

第三行 $m$ 个非严格升序排列的正整数 $b_i$，表示第二列中每瓶牛奶的重量；

第四行一个正整数 $q$，表示询问的次数；

接下来 $q$ 行，每行 $5$ 个正整数 $l_1,r_1,l_2,r_2,k$，表示把第一列的 $l_1$ 到 $r_1$ 瓶和第二列的 $l_2$ 到 $r_2$ 瓶放在一列，询问第 $k$ 轻的牛奶。输入数据保证 $k≤r_1−l_1+r_2−l_2+2$，且 $l_1≤r_1,l_2≤r_2$。

（非严格升序指可能有相同元素）

输出格式

输出共 $q$ 行，每行一个正整数，表示询问中第 $k$ 轻的牛奶重量。

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

1
3

数据范围

保证所有 $a_i,b_i≤10^8$