3637. 解密信件（递归回溯）

3637. 解密信件（递归回溯）

oxx 总是喜欢给 ultmaster 写信，由于某些原因，这些信的内容又不能被人看见。但传信的过程中，信中信息的泄露又不可避免，于是 oxx 发明了一种信内容信息的加密方式。ultmaster 拿到了 oxx 的加密程序：

char letter[]; void encrypt(l, r) { if (l < r) { reverse letter[l..r]; k = (r - l + 1) / 2; encrypt(l, l + k - 1); encrypt(l + k, r); } }

其中 ​​reverse letter[l..r]​​​ 是将 ​​letter​​ 从 l 到 r（闭区间）的子串倒置。

对于某个长度为 n，下标从 1 开始的字符串要进行加密，只要调用 ​​encrypt(1, n)​​ 即可。

由于 ultmaster 有超强的理解能力，所以 ultmaster 只需要知道信里面某些位置的信息，就能得知整封信的内容。而 oxx 写了太多的信给 ultmaster 。所以 ultmaster 会有 T 次询问，每一次询问其中一封信的一个位置 x，表示加密后的信里的位置，他想知道这个位置在加密前的信里是在什么位置。

众所周知，oxx 有很多话想说，所以信会很长很长。

Input

第一行一个整数 T (1≤T≤1 000)，表示询问的个数。

接下来的 T 行，每行两个整数 n 和 x (1≤x≤n≤1018)，表示信的长度和询问的位置。

Output

包含 T 行，每行一个整数，表示对于每一个询问的答案。

Examples

input

4 4 1 4 2 4 3 4 4

output

3 4 1 2

Note

样例解释：1234 → 43|21 → 3|4|1|2.

题目大概：

给出加密的字母的位置，要求给出它的原来位置。

思路：

它是递归加密，那么用回溯来解密。

代码：

#include using namespace std;#define ll long longconst int mod=1e9+7;const int maxn=2e5+10;const double pi=acos(-1.0);ll dfs(ll l, ll r,ll x){ if (l < r) { ll k = (r - l + 1) / 2; if(x

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。