#1285. eileen的小把戏

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 丸山彩

题目描述

乃琳和Tom分别写下了两个整数序列 A,BA,B(有可能存在 00 或者负数),元素个数分别为 n,mn,m

Tom从 A,BA,B 中各选一个元素 Ai,Bj (1in, 1jm)A_i, B_j\ (1\leq i \leq n,\ 1\leq j \leq m),使得它们的乘积最大。

但是乃琳想让这个乘积尽可能小。在Tom计算乘积之前,乃琳偷偷盖住了序列 AA 中的一个数。如果有多种选择,乃琳会盖住可选的任意一个最大的数。

可怜的Tom,被她玩弄于股掌之中,请帮助Tom看一下哪个数被盖住了,然后计算一下此时的乘积最大值。

输入格式

第一行两个正整数 n,m (2n2105, 1m2105)n,m\ (2\leq n \leq2\cdot 10^5,\ 1\leq m \leq2\cdot 10^5),用空格分开。

第二行 nn 个整数用空格分开,代表 AA 中的元素 A1...An (109Ai109)A_1...A_n\ (-10^{9}\leq A_i \leq 10^9)

第三行 mm 个整数用空格分开,代表 BB 中的元素 B1...Bm (109Bi109)B_1...B_m\ (-10^{9}\leq B_i \leq 10^9)

输出格式

一行两个整数,用空格隔开,代表被盖住的数和此时的最大值。

样例

样例输入1

2 2
20 18
2 14

样例输出1

20 252

样例输入2

5 3
-1 0 1 2 -3
-1 0 1

样例输出2

-3 2

样例输入3

2 2
1 2
-1 -2

样例输出3

1 -2