题目描述

小码哥有两个长度为$n$的序列$a,b$，他想要对这两个序列做一些运算。

首先，小码哥得到了一个$n\times n$的表格$M$，其中$M_{ij}=a_i\times b_j$。

然后，他会给出一个区间$[l,r]$，然后他会得到$a,b$的子区间$a_l,a_{l+1},…,a_r$和$b_l,b_{l+1},…,b_r$，不妨记$k=r-l+1$，则这两个子区间在表格$M$中对应了其中一个$k\times k$的区域。

小码哥会给出$m$次询问，每次询问都会给出一个区间$[l,r]$，他想知道，每次询问在表格$M$中对应的区域中，最大值和最小值分别是多少。

输入格式

第一行输入两个整数$n,m$； 第二行输入$n$个整数$a_i$； 第三行输入$n$个整数$b_i$； 接下来$m$行，每行输入两个整数$l,r$，表示一次询问的区间。

输出格式

输出共$m$行，每行输出两个整数，分别代表询问最大值和最小值。

样例输入 #1

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

样例输出 #1

20 -25
12 -16
15 -12

说明/提示

对于20%的数据，有$1\leq n,m\leq 100$； 对于100%的数据，有$1\leq n,m\leq 10^5,1\leq l\leq r\leq n,-10^9\leq a_i,b_i\leq 10^9$。