有 n 个人坐成一排开会，编号从 1 到 n，第 i 个人基础能力是 a_i。第 i 个人与第 i-1 个人的沟通速率为 b_i。区间在 [l,r],l < r 的人可以组成讨论组，若讨论组内沟通速率均不小于 k，即 b_{l+1},b_{l+2},\cdots,b_r\ge k，则该讨论组的等级是 k。在讨论组内任选两个人 u,v，他们的贡献是 a_ua_v，则该讨论组的贡献是最大的 a_ua_v。

有 n 个询问，每次问对给定的等级 x，能成立多少个至少 x 级的讨论组，以及所有这些讨论组里，贡献最大的组贡献是多少。

输入一行一个整数 n(1\le n\le 10^6)。

接下来输入一行 n 个整数，第 i 个整数代表 a_i(|a_i|\le10^9)。

接下来输入一行 n-1 个整数，第 i 个整数 b_{i+1}(1\le b_{i+1} < n) 且保证 b 值域连续，即若存在某个 b_j=c，则对所有 1\le c'< c 必然存在至少一个整数 b_k=c'。

输出 n 行，第 i 行输出两个整数，为等级 i 的讨论组数目和等级 i 的最大贡献讨论组的贡献值。

对样例一：

对 x=3 ，有且仅有讨论组 [2,3],[6,7],[9,10]，故有 3 个讨论组，且最大贡献在 [2,3] 取得，为 4\times8=32。

对 x=2，有讨论组 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[6,7],[6,8],[7,8],[9,10]，共 10 个，最大值可以在讨论组 [1,3] 取得 7\times8=56，也可以在 [1,4] 取得。

对 x=1，所有 C_n^2=45 个讨论组都可行，最大值为 8\times9=72。