本题为问题的困难版本，两题的唯一区别在于不舒适度的定义。 给定 首歌的两种难度版本的难度系数 ，小红可以任选一个版本游玩。然而，当小红的能力为 时： 如果歌的难度 大于 ，小红会获得 的不舒适度； 如果歌的难度 小于 ，小红会获得 的不舒适度； 如果歌的难度 在 之间，那么这首歌不会产生不舒适度。 现在，有 次询问，第 次询问包含一个整数 ，你需要回答当小红的能力为 时，以最优策略游玩这 首歌后不舒适度的最小值。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入两个整数 ，表示歌曲数量、询问次数。此后 行，第 行输入两个整数 ，表示第 首歌的两个不同难度版本的难度系数。此后 行，第 行输入一个整数 ，表示第 次询问的能力值。除此之外，保证单个测试文件的 之和、 之和均不超过 。

输出描述:

对于每组测试数据，在一行上输出 个整数，表示每个询问的答案。