3685. 线段树

单点时限: 2.0 sec

内存限制: 512 MB

QQ 小方以前不会建立线段树,现在他会了,所以他急切的想教会你。

建立线段树的代码是这样的:

function build(l, r, x):
  init node x
  if l < r then:
    mid = floor((l + r) / 2)
    build(l, mid, x * 2)
    build(mid + 1, r, x * 2 + 1)

单单讲给你听肯定是不够的,为了表现自己,QQ 小方现在要考考你。

他会给你一个区间 $[l,r]$ ,现在 QQ 小方让你告诉他最小的 $n$ ,使得进行 build(1, n, 1) 操作的时候,线段树上某一个结点恰好表示该区间(即在build(1, n, 1)操作时,某时刻参数 $l$ 和 $r$ 恰好是给出区间的两个端点)。当然,QQ 小方并不想为难你,他只想让你在范围 $[1,2 \cdot 10^9]$ 内找 $n$,如果在这个范围内仍然没有 $n$,你只需要告诉他不存在。

输入格式

输入数据第一行包含一个整数 $T$ ($1\le T\le 500$),表示数据组数。

接下来的 $T$ 行,每行包含两个整数 $l,r$ ($1\le l\le r\le 10^9$, $\left \lfloor \frac{l}{r-l+1} \right \rfloor \le 1000$),表示给出的区间。

输出格式

对于每组数据输出一行包含一个整数,表示答案。如果在 $[1,2\cdot 10^9]$ 范围内不存在这样的答案,输出 $-1$。

样例

Input
2
1 3
2 3
Output
3
-1

96 人解决,218 人已尝试。

120 份提交通过,共有 1562 份提交。

5.3 EMB 奖励。

创建: 5 年,1 月前.

修改: 5 年,1 月前.

最后提交: 10 月,2 周前.

来源: N/A

题目标签