U637905 三角洲高手的超能力 (Hard Version)

*“如果能早点拥有这个能力，就不会堵桥失败了！”* 612寝室的三角洲高手在某一天发现自己觉醒了一个能力，他能一瞬间看出游戏中敌人的技术值，于是他利用自己的这个能力，在游戏中所向披靡。 这一天，李伟峰正在堵桥，他准备利用这个能力来决定要不要出击。

（注：本题为困难版本） 李伟峰看穿了 $N$ 个敌人的技术值。 接下来李伟峰会进行 $K$ 次查询。每次查询会给出一个技术值 $d_i$。 你需要迅速回答： 有多少个**其他**敌人的技术值**严格大于**该技术值？ 有多少个**其他**敌人的技术值**严格小于**该技术值？

第一行包含两个整数 $N, K$ ($1 \le N, K \le 5 \times 10^6$)。 第二行包含 $N$ 个整数 $h_i$ ($1 \le h_i \le 10^7$)。 接下来 $K$ 行，每行一个整数 $d_i$（$1 \le d_i \le 10^7$）。

对于每次查询，在一行输出两个整数，中间用空格隔开：分别代表大于该值的人数，以及小于该值的人数。

**数据范围** * $1 \le N, K \le 5 \times 10^6$ * $1 \le h_i \le 10^7$