瓦卡分水果

• 输入文件：fruits.in
• 输出文件：fruits.out
• 时间限制：1 second
• 空间限制：512 megabytes

阿瓦和阿卡各批发了一些水果作为奖品，阿瓦将自己的水果称为智慧水果，阿卡将自己的水果称为活力水果。每一位获奖者都会获得一个智慧水果和一个活力水果。

阿瓦和阿卡批发的水果每一个都不一样，阿瓦一共批发了 $n$ 种水果，其中第 $i$ 种水果的智慧值为 $P_i$。阿卡一共批发了 $m$ 种水果，其中第 $i$ 种水果的活力值为 $Q_i$。如果一个获奖者拿到的是智慧水果 $i$ 和活力水果 $j$，那么他的开心程度就是 $P_i + Q_j$。

每位获奖者获奖的大小都不同，阿瓦和阿卡为了公平，当然是希望获奖越大的选手越开心啦！但同时每个选手都希望互相之间拿到的水果组合都不同，即如果有两个人拿到的智慧水果相同，那么他们拿到的活力水果一定不同。如果两个人拿到的活力水果相同，那么他们拿到的智慧水果一定不同。很显然，这样最多有 $n \times m$ 种组合方法。阿瓦和阿卡将这些方法可以造成的开心程度从大到小排序之后，按照获奖的大小依次发给选手。

他们想要考考你，发出去的前 $K$ 个水果组合给获奖者带来的开心程度是多少。

Input

第一行三个数 $n,m,K$，意义如题面中所述。

第二行 $n$ 个数，第 $i$ 个数 $P_i$ 表示第 $i$ 种智慧水果的智慧值。

第三行 $m$ 个数，第 $i$ 个数 $Q_i$ 表示第 $i$ 种活力水果的活力值。

Output

输出 $K$ 行，第 $i$ 行一个数表示第 $i$ 个发出去的水果组合能带来的开心程度。

Example

input

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

output

9
8
8
7

Constraints

对于 $30\%$ 的数据，$n,m \le 10^3$。

另有 $20\%$ 的数据满足，$K \le 2$。

对于 $100\%$ 的数据，$n,m,K \le 10^5$，$0 < P_i, Q_i \le 10^7$，$K \le n \times m$。