題干：

Let's denote as??the number of bits set ('1' bits) in the binary representation of the non-negative integer?x.

You are given multiple queries consisting of pairs of integers?l?and?r. For each query, find the?x, such that?l?≤?x?≤?r, and??is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer?n?— the number of queries (1?≤?n?≤?10000).

Each of the following?n?lines contain two integers?li,?ri?— the arguments for the corresponding query (0?≤?li?≤?ri?≤?1018).

Output

For each query print the answer in a separate line.

Examples

Input

3 1 2 2 4 1 10

Output

1 3 7

Note

The binary representations of numbers from 1 to 10 are listed below:

題目大意：

我們定義表示數(shù)x在二進(jìn)制表示下所有數(shù)位中1的個(gè)數(shù)。

現(xiàn)在給定兩個(gè)整數(shù)?l?和r。希望找到一個(gè)?x，滿足?l?≤?x?≤?r，并且的值最大。如果有多種方案輸出最小的一種。

解題報(bào)告：

? ?貪心處理，并且他這個(gè)：If there are multiple such numbers find the smallest of them.也給了提示，需要從小到大貪心。對(duì)于這個(gè)題我們不需要首先關(guān)注這個(gè)值是多少，而是關(guān)注值中有多少個(gè)1（因?yàn)槭紫容敵?最多的數(shù)字）。我們可以采用上下界貪心的思路，最小的值肯定是 l ，答案肯定不會(huì)少于l，并且答案首先最少就是popcount( l )，然后我們依次增加答案并且保證構(gòu)造的是最小值，怎么做到呢？就是從低位到高位按位增加一個(gè)1。依次類推 就完事了。注意寫法。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n,x,y,a[MAX],ans; int main() {ll n,l,r;cin>>n;while(n--) {scanf("%lld%lld",&l,&r);ll ans = 0;ll bit = 1;while(l<=r) {ans = l;l |= bit;bit<<=1;}printf("%lld\n",ans);} return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 485C】Bits （二进制相关，数学，贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。